Pathfinding without target (prolog)

Bc19c63f45f2ff4e799095a8ec57a641
0
Moltar 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.

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

Moltar

5 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 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.

4413189eb92ecb0c72aa193596bda383
0
Trap_D 101 Jan 07, 2007 at 12:20

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).

Bc19c63f45f2ff4e799095a8ec57a641
0
Moltar 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 ;-)

Fe76116c2453dd04043c163cf01e1e5e
0
itsbrian 101 Jan 16, 2007 at 00:05

@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).

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

4413189eb92ecb0c72aa193596bda383
0
Trap_D 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: