Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Pathfinding: Filling a matrix with numbers

Credits go to anonymous, CGamesPlay, Don Freeman, Goalie Ca, jason perkins, Johan Halmén, Neil Walker, piccolo, Schyfis, Thomas Fjellstrom, tobing, Trent Gamblin, weapon_S, and X-G for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
Pathfinding: Filling a matrix with numbers
Paul whoknows
Member #5,081
September 2004
avatar

I want to know how these matrices were filled in.

60691298se6.png

http://www.allegro.cc/files/attachment/597661

I mean, which pattern was used?

Please, omit links to A*, and Dijkstra's algorithm (I already read some of them), I want to know a straight and quick way to fill a bidimentional array with those numbers in order to find the shortest path between two cells.

Thanks in advance.

EDIT

Particularly I don't understand the 'jump' from 6 to 14 in the second matrix. Start from the green cell, you'll see it goes from 0 to 6 and after the unwalkable cell it jumps to 14, I really don't get it.

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

Don Freeman
Member #5,110
October 2004
avatar

It is counting how much movement was needed to get to each point. They reason for the jump from 6 to 14, is that if you where to walk around the blocked path, that is the total movement needed to get there.8-) And yes, most likely it was A*.:P A* itself is easy to understand...it is implementing it that is hard, at least for me. I don't really know much about trees and such, so it has been my downfall so far.

--
"Everyone tells me I should forget about you, you don’t deserve me. They’re right, you don’t deserve me, but I deserve you."
"It’s so simple to be wise. Just think of something stupid to say and then don’t say it."

CGamesPlay
Member #2,559
July 2002
avatar

Quote:

I want to know a straight and quick way to fill a bidimentional array with those numbers in order to find the shortest path between two cells.

You use Dijkstra's algorithm :P Both of the images you posted are the result of Dijkstra's algorithm.

The end point has a distance of 0. Any space touching that origin that doesn't already have a distance filled in has a distance of 1. Any space touching one of those that doesn't already have a distance filled in has a distance of 2. And so on.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Goalie Ca
Member #2,579
July 2002
avatar

Quote:

You use Dijkstra's algorithm :P Both of the images you posted are the result of Dijkstra's algorithm.

Yup, sure seems like it. Sure its a hard algorithm to understand but after you get it, it is remarkably straight forward.

-------------
Bah weep granah weep nini bong!

Don Freeman
Member #5,110
October 2004
avatar

Here is another algorithm that looks pretty neat.:D

--
"Everyone tells me I should forget about you, you don’t deserve me. They’re right, you don’t deserve me, but I deserve you."
"It’s so simple to be wise. Just think of something stupid to say and then don’t say it."

Schyfis
Member #9,752
May 2008
avatar

But it's not nearly as hard to pronounce, so therefore it must not be as efficient.

________________________________________________________________________________________________________
[freedwill.us]
[unTied Games]

Trent Gamblin
Member #261
April 2000
avatar

Any baseball fan knows it's dike-stra! :)

Paul whoknows
Member #5,081
September 2004
avatar

Quote:

The end point has a distance of 0. Any space touching that origin that doesn't already have a distance filled in has a distance of 1. Any space touching one of those that doesn't already have a distance filled in has a distance of 2. And so on.

So you mean something like this:?

0 1 0
1 0 1
0 1 0

2 1 2
1 0 1
2 1 2

0 3 0 3 0 
3 2 1 2 3
0 1 0 1 0
3 2 1 2 3
0 3 0 3 0

4 3 2 3 4 
3 2 1 2 3
0 1 0 1 2
3 2 1 2 3
4 3 0 3 4

??? my head hurts!
Oh, BTW, what happens when I find an unwalkable cell?

EDIT


How was that 4 calculated?( look at the yellow circle)


http://www.allegro.cc/files/attachment/597662

It seems, I am having problems to understand what should I do when I find an non-walkable cell.

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

jason perkins
Member #10,586
January 2009

The idea to me seems pretty easy but I'm sure the algorithm is hard to implement if you start in the middle of this and can only walk in a strait line....

212
101
212

going up down left or right takes 1 move, going up then right takes 2...

and if there's a wall..

43234|6
32123|5
2101234
3212345

Its like walking around with the arrow keys and typing the next number every time you go.

Sorry if that doesn't help, I'm newb but I figured I'd at least try :P

Thomas Fjellstrom
Member #476
June 2000
avatar

Quote:

It seems, I am having problems to understand what should I do when I find an non-walkable cell.

You ignore it. You can't travel over it, so the algorithm either skips it or gives it a rather high value. And the code selects the cells that have the LOWEST value to move to. It doesn't "jump" to 14, see how each diagonal is 2, because if you travel in horizontal and vertical movements it takes two moves (two cells).

Quote:

How was that 4 calculated?( look at the yellow circle)

Look at the numbers in the cells leading from the origin, its a simple increasing count. Each cell is worth one. In the end, the final path is chosen by selecting the path with the lowest total path sum.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

CGamesPlay
Member #2,559
July 2002
avatar

Quote:

2 1 2
1 0 1
2 1 2

0 3 0 3 0 
3 2 1 2 3
0 1 0 1 0
3 2 1 2 3
0 3 0 3 0

You made an error here. You skipped the 0's in the middle of every edge. It should look like this:

0 3 2 3 0 
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
0 3 2 3 0

Let's add an unwalkable space on this simple graph. 0 is the start point, and the X is unwalkable:

. . . . X . . 0 . . . . . X . 1 0 1 . . . 2 X 2 1 0 1 3 . 3 2 X 2 1 0 1 3 4 3 2 X 2 1 0 1

Since at this point there are no nodes that are touching the current nodes that haven't been visited (there are no .s immediately nearby), we are done.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Johan Halmén
Member #1,550
September 2001

Use a recursive function. Fill all cells with a step value = 1E99. Then start at the zero cell and set its step value to 0.

Then recursively check each neighbour cell. If their step value is higher than this+1, set them to this+1 and check them in turn recursively.

[edit]
The recursion will easily go on a depth-first pattern, which probably is not good. You should first set all neighbour cell step values to this+1 (unless they are already lower than this+1), then you go further in the recursion into each neighbour that got the this+1 value.

[edit2]
If you have a start and end cell defined, compare the this+1 value with the value you have in the end cell. No use going further in a neighbour cell if its step value is already higher than the value you have in the end cell. I guess this is already very much like Dijkstra.
Your smaller matrix, that ends with 11 steps, seems to have found the 11 step to the target in an early stage. All paths to any direction seems to have stopped at number 11.
In the larger matrix the path length to the target is 19, but the corner cell contains the step value 22. My guess is that this algo has traversed all cells, even though the target cell was found in an earlier stage. The red marked path is a bit missleading. If one can travel diagonally, it should be noticed in the step values, too. And steps 8-10-12 are questionable, due to the wall.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

piccolo
Member #3,163
January 2003
avatar

to understand this fully you need the outer row and coulum labels.
and the rest of the matrices that got you there.

Quote:

Oh, BTW, what happens when I find an unwalkable cell?

it should be marked as infinity.

there are to type of path algorithms

find all the paths

or find

one path

wow
-------------------------------
i am who you are not am i

Neil Walker
Member #210
April 2000
avatar

Isn't A* essentially just the same as Dijkstra but with the benefit of heuristics to favour the quicker and better path?

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

CGamesPlay
Member #2,559
July 2002
avatar

No. A* is similar to Dijkstra's but it quits once it hits the goal node (also, you run it in reverse, but that doesn't affect the outcome).

Both algorithms are breadth-first searches, but Dijkstra's goal is to find the shortest path from one point to every other point, where A*'s goal is to find the shortest past from one point to exactly one other point.

So, in a way, what piccolo just said was right, except that the two types of algorithms are really the same time, just with one you don't need to do all the work of the second. Either way, once you know Dijkstra's, you have the solution you need.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

anonymous
Member #8025
November 2006

Some nice challenges on pathfinding, 81, 82, 83.

They can be solved in a rather similar way, though, so I don't entirely understand why they consider some more challenging.

X-G
Member #856
December 2000
avatar

Quote:

No. A* is similar to Dijkstra's but it quits once it hits the goal node (also, you run it in reverse, but that doesn't affect the outcome).

Actually, Dijkstra's algorithm is just a special case of A* without a heuristic.

--
Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散!悪霊退散!怨霊、物の怪、困った時は ドーマン!セーマン!ドーマン!セーマン! 直ぐに呼びましょう陰陽師レッツゴー!

Neil Walker
Member #210
April 2000
avatar

So it's A*-- ;)

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

CGamesPlay
Member #2,559
July 2002
avatar

Quote:

Actually, Dijkstra's algorithm is just a special case of A* without a heuristic.

It is without a heuristic, but Dijkstra's finds the shortest path to every possible node from a single source, where A* finds the shortest path from one source to one goal.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

X-G
Member #856
December 2000
avatar

You can stop Dijkstra's algorithm when you have found the node you want, and you can keep going with A* until you have information for every node. They are not different in that regard.

--
Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散!悪霊退散!怨霊、物の怪、困った時は ドーマン!セーマン!ドーマン!セーマン! 直ぐに呼びましょう陰陽師レッツゴー!

tobing
Member #5,213
November 2004
avatar

The purpose of A* is to find what is guessed or estimated to be the shortest path. If the path is found, it will be the shortest path (if that's the metric used). However, the key thing in A* is bounding: The algorithm estimates the remaining length from any node and doesn't pursue that node as long as others seem to estimate a shorter remaining path. So the bounding tries to cut all alternatives that will be too long.

The advantage is that you find the shortest path more quickly. In contrast, Dijkstra does find the shortest path, but in the worst case you will find all other possible paths before you're done.

There's a downside, of course. If the shortest path has to run around more complex obstacles, the A* bounding may give wrong guidance. In that case, A* might take even longer than Dijkstra.

So, A* is very good in many situations, but can be bad in some.

This article has a nice explanation of the algorithm with pictures:
http://www.policyalmanac.org/games/aStarTutorial.htm
and it is from Amit's Gameprogramming Site, which has tons of good infos:
http://www-cs-students.stanford.edu/~amitp/gameprog.html

CGamesPlay
Member #2,559
July 2002
avatar

I just finished a visual demonstration of the algorithm on a rectangular grid (all the other demonstrations weren't as descriptive and were made in Java). Check it out.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

weapon_S
Member #7,859
October 2006
avatar

Paul whoknows
Member #5,081
September 2004
avatar

CGamesPlay thank you very very much! it's impossible not to understand this algorithm with your explanation! Thanks!!!! :-*

[EDIT]

Just one more question, what does that mean setting a node to infinity?

____

"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.

CGamesPlay
Member #2,559
July 2002
avatar

Basically, if a node's distance value is infinity (you could also use -1 or any other special value), then you know that you haven't "visited" that node yet. You can then skip the step of "marking each node as unvisited", since you know that if the distance is that special value, then the node hasn't been updated yet.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

 1   2 


Go to: