dcsimg
A Flash Developer Resource Site

Results 1 to 8 of 8

Thread: Dijkstra's Algorithm

  1. #1
    Junior Member
    Join Date
    May 2010
    Posts
    4

    Question 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.

    MyFlashFolder (Readme inside)

    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. #2
    talk to the hand! Never_land:('s Avatar
    Join Date
    Nov 2007
    Location
    your mother's bedroom
    Posts
    490
    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?
    Last edited by Never_land:(; 05-25-2010 at 12:45 PM.

  3. #3
    Junior Member
    Join Date
    May 2010
    Posts
    4
    if you mean you can edit it yeah sure, the algorithm was in pseudo-code i just kinda translated it.

  4. #4
    An FKer
    Join Date
    Sep 2005
    Location
    Ontario
    Posts
    1,167
    Can you type out your pseudo of how you're going about programming it? Maybe it's just a matter of concept.

  5. #5
    Junior Member
    Join Date
    May 2010
    Posts
    4
    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. #6
    An FKer
    Join Date
    Sep 2005
    Location
    Ontario
    Posts
    1,167
    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.
    Last edited by Osteel; 05-27-2010 at 01:46 PM.

  7. #7
    Funkalicious TOdorus's Avatar
    Join Date
    Nov 2006
    Location
    Nijmegen, Netherlands
    Posts
    697
    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;
    		addToOpenList(childNode);
    	}
    }
    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. #8
    Junior Member
    Join Date
    May 2010
    Posts
    4
    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
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center