0
101 Jan 06, 2007 at 20:56

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

#### 5 Replies

0
167 Jan 06, 2007 at 23:18

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.

0
101 Jan 07, 2007 at 12:20

http://jfoutelet.developpez.com/articles/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).

0
101 Jan 07, 2007 at 12:53

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

0
101 Jan 16, 2007 at 00:05

@Trap D

http://jfoutelet.developpez.com/articles/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!)

0
101 Jan 17, 2007 at 21:38

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

The limits of the translation :

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

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

:lol: