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. 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/597661I 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. EDITParticularly 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. --"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 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. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 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. ------------- Bah weep granah weep nini bong!
 Don Freeman Member #5,110 October 2004 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 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 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!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/597662It 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....212101212going up down left or right takes 1 move, going up then right takes 2...and if there's a wall..43234|632123|521012343212345Its 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. -- 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 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 1Since 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 -
 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.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 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 Isn't A* essentially just the same as Dijkstra but with the benefit of heuristics to favour the quicker and better path? 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. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 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 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 So it's A*-- 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. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 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. -- Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散！悪霊退散！怨霊、物の怪、困った時は　ドーマン！セーマン！ドーマン！セーマン！　直ぐに呼びましょう陰陽師レッツゴー！
 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:http://www.policyalmanac.org/games/aStarTutorial.htmand 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 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 -
 weapon_S Member #7,859 October 2006
 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. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 1   2  Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads