# Pathfinding without target (prolog)

5 replies to this topic

### #1Moltar

New Member

• Members
• 2 posts

Posted 06 January 2007 - 08:56 PM

Hi!

I read about pathfinding. But in most algorithm solutions the start and target coordinates are known.
I'm making a board game. To offer the user all possible moves I need an algorithm the other way round.
Given is start coordinates and the number on the dice. Now I want my program to give me all possible moves for all my figures.
Best would be if the moves could be stored in a list.
I so far have the coordinates of the board fields and the function to find out if two fields are next to each (neighbours).
I would like to code the algorithm in prolog.

Moltar

### #2Reedbeta

DevMaster Staff

• 5344 posts
• LocationSanta Clara, CA

Posted 06 January 2007 - 11:18 PM

In Prolog this should be particularly easy. Just define a predicate that's true if two fields are a distance n from each other, by using induction (they are a distance 1 if adjacent, and distance n if adjacent to a field of distance n-1). Then you should be easily able to write the expression that finds all fields of distance n from your starting point.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3Trap D

Member

• Members
• 55 posts

Posted 07 January 2007 - 12:20 PM

http://jfoutelet.dev...ticles/partage/
You should read the part II C.
It shows how to obtain all the neihgtbourgs of a node in one, two, three ... steps (with little modifications to count the steps).

### #4Moltar

New Member

• Members
• 2 posts

Posted 07 January 2007 - 12:53 PM

Thanks for your help. Reedbetas solution works fine.
Thanks to Trap D, too. My French is even worse than my English ;-)

### #5itsbrian

New Member

• Members
• 16 posts

Posted 16 January 2007 - 12:05 AM

Trap D said:

http://jfoutelet.dev...ticles/partage/
You should read the part II C.
It shows how to obtain all the neihgtbourgs of a node in one, two, three ... steps (with little modifications to count the steps).

Here's the above link translated to english (text within diagrams remains untranslated ...now there's an idea for an AI project! ...in my crystal ball i see google implementing an OCR engine!)

### #6Trap D

Member

• Members
• 55 posts

Posted 17 January 2007 - 09:38 PM

It's funny to see my article in English :lol:

The limits of the translation :

Quote

?- sort([bouteille, bidon, verre, bouteilles], N).
N = [bidon, bouteille, bouteilles, verre]
Yes

Quote

leaves ([bottle, can, glass, bottles], NR).
NR = [can, bottle, bottles, glass]
Yes
:lol:

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users