|
This thread is locked; no one can reply to it. |
1
2
|
Pathfinding: Filling a matrix with numbers |
Paul whoknows
Member #5,081
September 2004
|
I want to know how these matrices were filled in. 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
|
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. -- |
CGamesPlay
Member #2,559
July 2002
|
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 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. -- Ryan Patterson - <http://cgamesplay.com/> |
Goalie Ca
Member #2,579
July 2002
|
Quote: You use Dijkstra's algorithm 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. ------------- |
Don Freeman
Member #5,110
October 2004
|
Here is another algorithm that looks pretty neat.:D -- |
Schyfis
Member #9,752
May 2008
|
But it's not nearly as hard to pronounce, so therefore it must not be as efficient. ________________________________________________________________________________________________________ |
Trent Gamblin
Member #261
April 2000
|
Any baseball fan knows it's dike-stra!
|
Paul whoknows
Member #5,081
September 2004
|
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! EDIT 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 going up down left or right takes 1 move, going up then right takes 2... and if there's a wall.. 43234|6 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 |
Thomas Fjellstrom
Member #476
June 2000
|
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. -- |
CGamesPlay
Member #2,559
July 2002
|
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. -- 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] [edit2] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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
|
to understand this fully you need the outer row and coulum labels. 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 |
Neil Walker
Member #210
April 2000
|
Isn't A* essentially just the same as Dijkstra but with the benefit of heuristics to favour the quicker and better path? Neil. wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie |
CGamesPlay
Member #2,559
July 2002
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
anonymous
Member #8025
November 2006
|
X-G
Member #856
December 2000
|
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. -- |
Neil Walker
Member #210
April 2000
|
So it's A*-- Neil. wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie |
CGamesPlay
Member #2,559
July 2002
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
X-G
Member #856
December 2000
|
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. -- |
tobing
Member #5,213
November 2004
|
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: |
CGamesPlay
Member #2,559
July 2002
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
weapon_S
Member #7,859
October 2006
|
CGames, that's some góód software |
Paul whoknows
Member #5,081
September 2004
|
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
|
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. -- Ryan Patterson - <http://cgamesplay.com/> |
|
1
2
|