Move from point x to point y alghoritm

ruby-talk
1

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.

xxxxxxxxxxxx
xxcxxxxxoxxx
xxxxxoxxxxxx
xxxxxxxxoxxx
xxxxxxxxxxxx
xxxxxxxxzxxx
xxxxxxxxxxxx

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.

xxxxxxxxxxxx
xxc----¬oxxx
xxxxxox!xxxx
xxxxxxx!oxxx
xxxxxxx-!xxx
xxxxxxxxzxxx
xxxxxxxxxxxx

Above is the best path that will be taken by the character, but first
he had to determine this way. First he has taken few approaches, like
this:

xxxxxxxxxxxx
xxc----¬oxxx
xxxxxox!-xxx
xxxxxxxxoxxx
xxxxxxxxxxxx
xxxxxxxxzxxx
xxxxxxxxxxxx

Hope you can understand me. I will appreciate your help. Thank you.

···

--
Posted via http://www.ruby-forum.com/.

2

Damián M. González wrote in post #1131525:

Hello fellows, how are you?

Very well, thank you :slight_smile:

I will appreciate your help. Thank you.

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.

···

--
Posted via http://www.ruby-forum.com/\.

3

Understood, thank you very much, I can see the light of this. :slight_smile:

···

--
Posted via http://www.ruby-forum.com/.

4

I've made the Lee alghoritm, work great. However I'm researching the
options. Thanks Abinoam Jr. and Regis for share knowledge.

···

--
Posted via http://www.ruby-forum.com/.

5

Hi Damián González,

You can search for Pathfinding algorithms.

I have recently solved a Project Euler problem with the A* (a-star) algorithm.

This blogpost explains it incredbly easy to understand.
http://www.policyalmanac.org/games/aStarTutorial_port.htm

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.

Abinoam Jr.

···

On Tue, Dec 24, 2013 at 1:53 PM, Damián M. González <lists@ruby-forum.com> wrote:

Understood, thank you very much, I can see the light of this. :slight_smile:

--
Posted via http://www.ruby-forum.com/\.

6

Abinoam Jr. wrote in post #1131570:

Hi Damin Gonzlez,

You can search for Pathfinding algorithms.
Pathfinding - Wikipedia

I have recently solved a Project Euler problem with the A* (a-star)
algorithm.

This blogpost explains it incredbly easy to understand.
http://www.policyalmanac.org/games/aStarTutorial_port.htm

Here code snippet fort a* :
http://branch14.org/snippets/a_star_in_ruby.html

···

--
Posted via http://www.ruby-forum.com/\.