Hello fellows, how are you?
I want to make you a question. Need your advice, just a clue about how
to look at this. This is a map, where “o” are collisions, and “c” is the
character, the “x” are walkable zones. “z” is the destination.
How will you face this problem: is needed to walk from point x to point
y. The character can’t walk through collisions. The character will
always priorize the x axis, so in this particular example will like to
take to the east(right), then when it reaches the x position of the
destination will walk through y axis until point z, which is
south(bottom). The character need to border a collision, as I said, it
can’t walk through any collision. Is wanted that if the character face a
collision and he(in some way) start to border it, if the x position of
the character is not equal to the x position of the destination the
character must try to return his way trough the x axys until reach the x
position of the destination. The character need to take the shorter way,
it’s meassured in steps, each step is a “zone” or “tile” walked. I’m not
looking for a resolution to this particular examples, I’m looking for an
alghoritm which will work in any case. I have some thouhgs but I’m not
sure if they are the best way to go. The method should return an #Array
with items #Symbols like this: [:east, :east, :east, :east, :south,
:south, :east, :south, :south]. This are the steps needed to do by the
charachter to reach his destination.
for this kind of algo, see ‘wave’ or ‘flood’ algorithm :
imagine some water which drop at your start position.
first particule which arrive to destination has take the
best path.
so if each particule memorize his path, you have the solution.
I think a-star is good for games because you can easily put a kind of
weight in each place of the map.
You can say “rivers have a cost of 3 to pass” and “plain terrain has a
cost of 1” and the algorithm will find the less costly of the paths.