A Flash Developer Resource Site

# Thread: Dijkstra's Algorithm

1. ## Dijkstra's Algorithm

I am currently trying to use Dijkstra's Algorithm for some pathfinding and I'm pretty sure it will work only, when i search my 12x12 map(144 tiles) it goes through the top left corner and freezes, giving me the abort script error message.

(ScreenShot)

I know this person uses Dijkstra's Algorithm in his program and it does not do that so I was wondering what I did wrong.

I think the problem is in the Thingy() function when im searching in all 8 directions.

Btw. I am using flash MX 6.0

2. I like this, it seems very usefull for AI's
I made something similar ages ago never got to fix a bug in it so I stopped, could there a way to make a... I guess I resolved the problem in my code just need to dig it out let me see if I can help, I might fix it around next week, too busy right now.

is this open source?

3. if you mean you can edit it yeah sure, the algorithm was in pseudo-code i just kinda translated it.

4. Can you type out your pseudo of how you're going about programming it? Maybe it's just a matter of concept.

5. Well i started with the A* and moved to this one but ill try to re-un-code it.
so here it goes 10:01

Make an Open and Closed Array(Open for the tiles being used and closed for the tiles that are "visited")

put the first tile in the open list(unless its a wall) and set its distance to 0

REPEAT
get the lowest distance score in the open list.

search each tile adjacent(all 8 directions) and add distance each time
1 for up,down,left,right and 1.41 for diagonal

if the adjacent tile is a wall or more that one space away from the current tile don't use it.

if it is useable put it in the open list and add the current tile to the closed list and as the parent for all the searched tiles

if the target is in the open list or open list is empty

end seacrch

go to Repeat

Once target is found trace parents back to starting

6. That seems about right. I tried looking at your code, but I'm really bad at reading other's code and trying to decipher it. If it helps here's my pseudo I used for this.

Begin by making your openList and closedList array. The openList contains the starting tile on which your character is standing. I also have another array used called holdOpen which you'll see soon. Also, the openList is a 2D array that contains the tile's name (obviously), but also the tile's parent name. Upon setup, it will contain: openList[0] = new Array("b"+startRow+"_"+startCol,"none")

Within my function findPath(), I do the following repeats. Note that this is used to find movable areas from the character, since the game is a different genre, though it's simply a matter of switching from breaking out of the loop to when you find the target.

1. Create a loop to cycle through the entire openList: for(p=0;p<openList.length;p++){. At the beginning, this will only contain your character tile.

2. Note that for mine, there is only four directional movement. But can easily be included to have the diagonals by adding the values you have for yours. Create another loop to quickly store the four (or eight) tiles into a temporary array called checkTiles. Now we can play with these tiles all at once.

3. Now we begin the following tests on each of these tiles stored in checkTiles. In order for a tile to be able to reach, they must pass all these tests. Make a loop through these tiles (again, eight times), and check the following on each tile stored in checkTiles[ i].

closedList :: isClosed = false
Loop through the closedList and see if there's a tile on their that matches the name of the current tile your checking in checkTiles. If so, set isClosed=true and break; this loop. No point checking through the rest of the closedList since we found a match. Save some time.

Walkable :: walkable = false
Simply check your map array to see if the the tile your checking is walkable. Since my tiles are named b1_1, extracting the x/y value to check the map array is simple. If it is walkable, then set walkable = true

holdOpen :: onHoldOpen = false
I'll explain this array next, but for now simply loop through and check, as you did the closedList if the current tile your checking on checkTiles is contained in this array. If so, set onHoldOpen = true and break; the loop, as we already found a match.

Because of the nature of my example I linked you, I have a few other tests I've added, included distance and height restrictions. You can always add more tests depending on your game as well. So now with these tests done, we can move on.

If all the tests have passed for this current tile on checkTiles, that is: isClosed = false, walkable = true, holdOpen = false, then we move to do the following. This might get a little confusing, so I'm going to try my best to explain it! The holdOpen array is a temporary storage for successful tiles being checked, so that they're not checked multiple times if they already pass. This is so it doesn't slow down the algorithm and end up finding a worse route (I believe anyways).

So taking the current tile that has passed in checkTiles (remember, we're still looping through them), we add a new array into the last element of the holdOpen array: holdOpen[holdOpen.length], making it a 2D array. Inside this, we'll store the same two elements we do in our openArray:

holdOpen[holdOpen.length] = new Array(checkTile[ i],openList[p][0]);. Remember, we're still looping the overall loop through the entire openList. Every time that loop ticks, we're checking a different tile, in which we check the eight new tiles around it in checkTile. So again, these two elements are the tiles name and the tiles parent.

Once the loop for checkTiles has completed all eight cycles, and before the loop for the openList cycles through to the next one, we add the current tile on the openList to the closedList. Remember, we're adding an array to the closedList, storing both the current openList's name and it's parent. The loop through the openList then cycles and we begin again on a new base tile, checking it's eight sides, and so on an so forth. Once all the tiles on the open list are checked (remember, there will only be one to start with!), we can move on.

We now clear the openList, we don't need the old one anymore, so just redeclare it openList = new Array();. Now, we loop through the length of holdOpen. The reason why it's the length and not a number of eight, is because not all the tiles we checked would have passed. So in otherwords, holdOpen contains all the successful tiles for the current base tile we're checking in the openList.

Anyways, we loop through holdOpen and store these arrays back into the openList to create our new list to check through. Redeclare: holdOpen = new Array(); so that it's empty for the next use when we run our tests.

That is about it. You continuing looping, through the openList until one of the checkTiles is the target, in which case you just break the entire loop and go straight to that tile. Or, if the openList is empty, meaning there were no more tiles to go to in attempts to find the target.

Assuming that the target was found, we do the following to trace it back using a created tracePath() function. Remember how, in our closedList we stored arrays, for both the tile name and the parent name? Well this is where it'll come into use. Simply loop through from the target, moving back to it's parent and to that parent's parent, etc etc, until you reach the start tile. You have found your route!

Now, I know this is probably extremely confusing. To be honest, I have trouble still understanding it. I took me over a month, and about twenty tries (that is, complete deletion and restarts) before I was able to get it. It was very frustrating. But, with a lot of explanation from people here (<3) and on another board, I was able to work my way through it.

So in conclusion, here is our pseudo:

PHP Code:
``` openList = new Array();openList[0] = new Array(tileName,no parent)closedList = new Array();holdOpen = new Array();// Loop through function until target is found or openList is empty:function findPath(){     for (p=0;p<openList.length;p++){            checkTile = new Array();            for (i=0;i<8;i++){                checkTile[i] = // tile name of the eight sides            }            // Test time! ---------------------------------------------------            for (i=0;i<8;i++){                 // 1. Is not on the closed list                onClosed = false;            for (o=0;o<closedList.length;o++){                     //if closed                     onClosed = true;                     break;                }                // 2. Is walkable            walkable = false;            if ( [walkable] ){                       walkable = true;                }                // 5. Is not on holdOpen                // remember, holdOpen stores 2D arrays: the tile name and tile parent        onHoldOpen = false;        for (o=0;o<holdOpen.length;o++){            if (checkTile[i] == holdOpen[o][0]){                 onHoldOpen = true;                break;            }        }               // If all tests are passed, add to holdOpen        if (onClosed == false and walkable == true and onHoldOpen == false){            holdOpen[holdOpen.length] = new Array(checkTile[i],openList[p][0]);        }           } // Done looping through the eight directions -------------------------------------           // Add the current tile to the closedList       closedList[closedList.length] = new Array(openList[p][0], openList[p][1]);               } // Cycle the openList loop            // Once looping through the entire openList is done, we move and do the following:     // Move holdOpen over as the new openList        openList = new Array();    for (i=0;i<holdOpen.length;i++){        openList[i] = new Array (holdOpen[i][0],holdOpen[i][1])        }         // Refresh     holdOpen = new Array();} // End of Entire Function ----------------------  ```

Well. That was fun, and took a lot longer then I expected ... nearly an hour! But I really hope you manage to take away from it something that can help you. Like I said, I totally understand any frustration when it comes to pathfinding, because it's such a stumbling block one has to pass to really feel like they can accomplish their project.

Well, it was for me anyways.

Good luck, let me know what you think of my, now turned into, essay.

7. Way to pay it forward Osteel , but procedural programming with Dijkstra? Wow.

Why not create a grid filled with node objects?

Code:
```public class  Node
{
public var open:Boolean = false;
public var score:int = int.MAX_VALUE;
public var parent:Node = null;

public function Node():void {

}
///for resetting the grid instead of creating a new one
public function reset():void  {
open = false;
score = int.MAX_VALUE;
parent = null;
}
}```
When you extend the search by adding new nodes to the list, just set the open flag to true, so your algorithm knows it doesn't need to add it to the open list. I think this is your problem astgenator. Since you don't check if the previous node is already visited you keep adding it to the open list. This makes it go back and forth betwen two tiles. Somehow your checks don't catch that when you check tile 0,0. When you revisit a tile, you do still need to check if your new score is lower (as this means a more effecient path). You can actually use only that and skip the whole open/closed part alltogether. If a child revisits its parent, it's bound to have a higher score anyway.

Code:
```var neighbors:Array = grid.getNeighbors(x,y);
var i:int
var length:int = neighbors.length;
var childNode:Node;
var score:int;
for( i = 0; i < length ; i++){
childNode= neighbors[i];
score = parentNode.score + walkingCost;
if(score < childNode.score){
childNode.score = score;
}
}```
A* is actually Dijkstra's with a heuristic thrown in, so it doesn't check ALL the new nodes in every extension, just the most probable one. I was a bit surprised when you told you have actually already done A*.

8. well i havent already done A* just started with it. I failed with A* and just modded my code for dijkstra's. I'll try to use these codes, thanks alot for the help.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 » Home » Movies » Tutorials » Submissions » Board » Links » Reviews » Feedback » Gallery » Fonts » The Lounge » Sound Loops » Sound FX » About FK » Sitemap

Click Here to Expand Forum to Full Width