Pathfinding without target (prolog)

[Moltar]

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.

Thanks for your help. (and sorry for my bad English)

Moltar

[Reedbeta]

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.

[Trap D]

This article may be interesting for you, but it's in French.
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).

[Moltar]

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

[itsbrian]

This article may be interesting for you, but it's in French.
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!)

link (http://translate.google.com/translate?hl=en&sl=fr&u=http://jfoutelet.developpez.com/articles/partage/&sa=X&oi=translate&resnum=1&ct=result&prev=/search%3Fq%3D%2B%2522Un%2Bprobl%25C3%25A8me%2Bde%2 Bpartage%2Ben%2BProlog%2522%26hl%3Den%26lr%3D%26sa %3DG%26as_qdr%3Dall)

[Trap D]

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: