Results 1 to 14 of 14
  1. #1
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Question My A* Algorithm(code), How can I make it faster?

    I have been learning java for about a week now. Started doing things with path finding. Making a game to test out the code. Anyways, it doesn't sound like a lot but finding a path from a 2d map from 2,2 to 90, 90 where the map is 100x100 takes roughly .6 seconds on a PC; however this isn't quite the case when it comes to porting it over to a mobile device with a more limited CPU which takes roughly 1.5 minutes to complete the path with a random map generator that I created for the game as well.
    The map is fully generated and then paths are created going around every object, not just the "solid" tiles, as flowers/bushes are not impassable but don't want them on the road path. Currently FindLowestF function takes up more than 80% of the entire path finding algorithm time so I have been putting more focus on trying to not have to run that function or skipping it if it isn't needed. I increased its speed (on the PC) from 2 seconds to .6 seconds, (on a mobile device with severely limited CPU potential) from 3-4 minutes to 1.5. I have tried to use a vector to put the tiles into and just load the ones off the top with the lowest F value (score G+H) but it didn't increase speed at all, though didn't slow it down either, and I can't use arraylist as I am doing the game using J2ME and for some reason they didn't include arraylist. The code is posted below. Thanks for any help that can be given.

    Java Code:
        private int StartPathFinding(FindMAP MainVar, int Sx, int Sy, int Ex, int Ey) 
        {
            StartX = Sx;
            StartY = Sy;
            EndX = Ex;
            EndY = Ey;
            NoPath = 0;
            Start(MainVar);
            while (MainVar.map[MAPOpenList][EndY][EndX] != 1)
            {
                if (CheckNext(MainVar, FindLowestF(MainVar)) == -1)
                {
                    NoPath = 1;
                    ClearALL(MainVar);
                    SetupFolliage();
                    break;
                }
            }
            if (NoPath == 0)
                DefinePath(MainVar);
            return NoPath;
        }
    
        private void DrawPath(FindMAP MainVar, int[][] Path, String[] Turn, int Count) 
        {
            for (i = 0; i < Count; i++)
            {
                x = Path[i][0];
                y = Path[i][1];
                MainVar.map[MAPNumber][y][x] = 0;
                if (Turn[i].equals("DR") || Turn[i].equals("LU"))
                    MainVar.map[MAPNumber][y][x] = 3;
                if (Turn[i].equals("DL") || Turn[i].equals("RU"))
                    MainVar.map[MAPNumber][y][x] = 17;
                if (Turn[i].equals("UR") || Turn[i].equals("LD"))
                    MainVar.map[MAPNumber][y][x] = 9;
                if (Turn[i].equals("UL") || Turn[i].equals("RD"))
                    MainVar.map[MAPNumber][y][x] = 26;
                if (Turn[i].equals("U") || Turn[i].equals("D"))
                    MainVar.map[MAPNumber][y][x] = 8;
                if (Turn[i].equals("L") || Turn[i].equals("R"))
                    MainVar.map[MAPNumber][y][x] = 2;
            }
        }
    
        private void DefinePath(FindMAP MainVar) 
        {
            x = EndX;
            y = EndY;
            ox = 0;
            oy = 0;
            Count = 0;
            while (MainVar.map[MAPParentList][y][x] != y * MapMaxX + x)
            {
                MainVar.Final = ConvertXY(MainVar, MainVar.map[MAPParentList][y][x]);
                x = MainVar.Final[0];
                y = MainVar.Final[1];
                Count++;
            }
            x = EndX;
            y = EndY;
            int[][] Path = new int[Count][2];
            String[] Turn = new String[Count];
            Count = 0;
            while (MainVar.map[MAPParentList][y][x] != y * MapMaxX + x)
            {
                MainVar.Final = ConvertXY(MainVar, MainVar.map[MAPParentList][y][x]);
                ox = x;
                oy = y;
                x = Path[Count][0] = MainVar.Final[0];
                y = Path[Count][1] = MainVar.Final[1];
                MakeTurn(Turn, Count, ox, oy, x, y);
                Count++;
            }
            DrawPath(MainVar, Path, Turn, Count);
        }
    
        private void MakeTurn(String[] Turn, int Count, int ox, int oy, int x, int y) 
        {
            if (ox > x && oy == y)
                Turn[Count] = "L";
            if (ox < x && oy == y)
                Turn[Count] = "R";
            if (ox == x && oy > y)
                Turn[Count] = "U";
            if (ox == x && oy < y)
                Turn[Count] = "D";
            if (Count >= 1)
                if (!Turn[Count].equals(Turn[Count - 1]))
                    Turn[Count - 1] = Turn[Count].concat(Turn[Count - 1]);
        }
    
        private void Start(FindMAP MainVar) 
        {
            CreateClosedList(MainVar);
            MainVar.map[MAPOpenList][StartY][StartX] = 1;
            MainVar.map[MAPClosedList][EndY][EndX] = 0;
            SetParent(MainVar, StartX, StartY, StartX, StartY);
        }
    
        private void CreateClosedList(FindMAP MainVar) 
        {
            for (y = 0; y < MapMaxY; y++)
                for (x = 0; x < MapMaxX; x++)
                    if (MainVar.map[MAPCollide][y][x] == 1 || MainVar.map[MAPObjects][y][x] >= 0
                            || MainVar.map[MAPNumber][y][x] != 1)
                        MainVar.map[MAPClosedList][y][x] = 1;
        }
    
        private int FindLowestF(FindMAP MainVar)
        {
            if(FoundOpen == 0)
            {
                Lowest = MapMaxY * MapMaxX + MapMaxX + 1;
                for (y = 0; y < MapMaxY; y++)
                    for (x = 0; x < MapMaxX; x++)
                        if (MainVar.map[MAPOpenList][y][x] == 1)
                            if (MainVar.map[MAPFValue][y][x] < Lowest)
                            {
                                FoundOpen = 1;
                                Lowest = MainVar.map[MAPFValue][y][x];
                                NextToCheck = y * MapMaxX + x;
                            }
            }
            if (FoundOpen == 1)
            {
                FoundOpen = 0;
                return NextToCheck;
            }
            else
            {
                return -1;
            }
        }
    
        private int CheckNext(FindMAP MainVar, int index)
        {
            if (index == -1)
                return -1;
            x = index % MapMaxX;
            y = index / MapMaxX;
            Close(MainVar, x, y);
            for (iy = -1; iy <= 1; iy++)
                for (ix = -1; ix <= 1; ix++)
                    if (ix != iy && ix != -iy)
                        if (CheckBounds(x + ix, y + iy))
                            if (CheckLists(MainVar, x + ix, y + iy))
                                Open(MainVar, x + ix, y + iy, x, y);
            return 0;
        }
    
        private void Close(FindMAP MainVar, int x, int y) 
        {
            MainVar.map[MAPClosedList][y][x] = 1;
            MainVar.map[MAPOpenList][y][x] = 0;
        }
    
        private boolean CheckBounds(int x, int y)
        {
            if (x <= MapMaxX - 1 && x >= 0 && y <= MapMaxY - 1 && y >= 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    
        private boolean CheckLists(FindMAP MainVar, int x, int y) 
        {
            if (MainVar.map[MAPClosedList][y][x] == 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    
        private void Open(FindMAP MainVar, int x, int y, int ox, int oy) 
        {
            if (MainVar.map[MAPClosedList][y][x] != 1)
            {
                MainVar.map[MAPOpenList][y][x] = 1;
                SetParent(MainVar, x, y, ox, oy);
                DefineGHF(MainVar, x, y);
                if (MainVar.map[MAPFValue][y][x] <= Lowest)
                {
                    FoundOpen = 1;
                    Lowest = MainVar.map[MAPFValue][y][x];
                    NextToCheck = y * MapMaxX + x;
                }
            }
        }
    
        private void SetParent(FindMAP MainVar, int x, int y, int ox, int oy) 
        {
            MainVar.map[MAPParentList][y][x] = oy * MapMaxX + ox;
        }
    
        private void DefineGHF(FindMAP MainVar, int x, int y) 
        {
            MainVar.map[MAPGValue][y][x] = FindOrigin(MainVar, x, y);
            MainVar.map[MAPHValue][y][x] = FindDestination(x, y);
            MainVar.map[MAPFValue][y][x] = MainVar.map[MAPGValue][y][x] + MainVar.map[MAPHValue][y][x];
        }
    
        private int FindOrigin(FindMAP MainVar, int x, int y) 
        {
            ox = x;
            oy = y;
            x = MainVar.map[MAPParentList][oy][ox] % MapMaxX;
            y = MainVar.map[MAPParentList][oy][ox] / MapMaxX;
            Distance = MainVar.map[MAPGValue][y][x] + 10;
            return Distance;
        }
    
        private int[] ConvertXY(FindMAP MainVar, int index)
        {
            if (index == -1)
                return null;
            MainVar.XYFinal[0] = index % MapMaxX;
            MainVar.XYFinal[1] = index / MapMaxX;
            return MainVar.XYFinal;
        }
    
        private int FindDestination(int x, int y)
        {
            Distance = 0;
            Sx = x - EndX;
            Sy = y - EndY;
            if (Sx < 0)
                Sx = -Sx;
            if (Sy < 0)
                Sy = -Sy;
            Distance = Sx + Sy * 10;
            return Distance;
        }
    
        private void ClearALL(FindMAP MainVar) 
        {
            for (y = 0; y < 100; y++)
                for (x = 0; x < 100; x++)
                    for (i = 1; i <= 8; i++)
                        MainVar.map[i][y][x] = 0;
        }

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default

    One quick comment.
    Are the if tests in drawPath() mutually exclusive. IE only one can be true. They could be if/else if
    which would save a few lookups and compares

  3. #3
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    Yes, else if would work for DrawPath. Using "else if" instead of "if" brings the function execution time down to 5ms average from 10ms average on the mobile device which doubles the speed of that function. I'll have to remember to use else if where ever possible. Thanks.

    Java Code:
    private void DrawPath(FindMAP MainVar, int[][] Path, String[] Turn, int Count) 
        {
            for (i = 0; i < Count; i++)
            {
                x = Path[i][0];
                y = Path[i][1];
                MainVar.map[MAPNumber][y][x] = 0;
                if (Turn[i].equals("DR") || Turn[i].equals("LU"))
                    MainVar.map[MAPNumber][y][x] = 3;
                else if (Turn[i].equals("DL") || Turn[i].equals("RU"))
                    MainVar.map[MAPNumber][y][x] = 17;
                else if (Turn[i].equals("UR") || Turn[i].equals("LD"))
                    MainVar.map[MAPNumber][y][x] = 9;
                else if (Turn[i].equals("UL") || Turn[i].equals("RD"))
                    MainVar.map[MAPNumber][y][x] = 26;
                else if (Turn[i].equals("U") || Turn[i].equals("D"))
                    MainVar.map[MAPNumber][y][x] = 8;
                else if (Turn[i].equals("L") || Turn[i].equals("R"))
                    MainVar.map[MAPNumber][y][x] = 2;
            }
        }
    also changed another function to use less if statements
    Java Code:
    private void MakeTurn(String[] Turn, int Count, int ox, int oy, int x, int y) 
        {
            if (oy == y)
            {
                if (ox > x)
                    Turn[Count] = "L";
                else
                    Turn[Count] = "R";
            }
            else
            {
                if (oy > y)
                    Turn[Count] = "U";
                else
                    Turn[Count] = "D";
            }
            if (Count >= 1)
                if (!Turn[Count].equals(Turn[Count - 1]))
                    Turn[Count - 1] = Turn[Count].concat(Turn[Count - 1]);
        }
    I added some code to time each function and count how many times each function is called. These are the results:
    Java Code:
    StartPathFinding: called 1 time took 99,489ms (1 min 39.4 seconds) to execute
    CheckNext: called 5,366 times took 1,429ms (1.4 second) to execute
    ConvertXY: called 356 times took 5ms (.005 seconds) to execute
    FindLowestF: called 5366 times took 97,897ms (1 min 37.8 seconds) to execute
    DrawPath: called 1 time took 9ms (.009 seconds) to execute
    DefinePath: called 1 time took 23ms (.023 seconds) to execute
    MakeTurn: called 178 times took 5ms (.005 seconds) to execute
    Start: called 1 time took 83ms (.083 seconds) to execute
    CreateClosedList: called 1 time took 83ms (.083 seconds) to execute
    Close: called 5366 times took 36ms (.036 seconds) to execute
    CheckBounds: called 21,464 times took 63ms (.063 seconds) to execute
    CheckLists: called 21,464 times took 177ms (.177 seconds) to execute
    Open: called 7,682 times took 629ms (.629 Seconds) to execute
    SetParent: called 7,683 times took 51ms (.051 seconds) to execute
    DefineGHF: called 7,682 times took 360ms (.36 seconds) to execute
    FindOrigin: called 7,682 times took 104ms (.104 seconds) to execute
    FindDestination: called 7,682 times took 65ms (.065 seconds) to execute
    ClearALL: called 0 times took 0ms (0 seconds) to execute
    FindLowestF was skipped 2,875 times saving 112,988ms (1 min 52.9 seconds)
    These are the times on the mobile device used. As you can see FindLowestF is what is taking up the longest. In this case all but 1.592 seconds are used by just FindLowestF. It seems a vector should be faster as I would just have to take the first variable and that would be the lowest F value. Perhaps I used vector incorrectly.
    Last edited by 0circle0; 07-06-2011 at 06:15 AM.

  4. #4
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,931
    Rep Power
    19

    Default

    Java Code:
                Lowest = MapMaxY * MapMaxX + MapMaxX + 1;
                for (y = 0; y < MapMaxY; y++)
                    for (x = 0; x < MapMaxX; x++)
                        if (MainVar.map[MAPOpenList][y][x] == 1)
                            if (MainVar.map[MAPFValue][y][x] < Lowest)
                            {
                                FoundOpen = 1;
                                Lowest = MainVar.map[MAPFValue][y][x];
                                NextToCheck = y * MapMaxX + x;
                            }
    Couple of questions.
    What's FindMAP?
    What are MapMaxY and MapMaxX?

  5. #5
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    There was more to FindMAP it had the entire algorithm in it, but I took everything out.
    Java Code:
    private int MapMaxY = 100, MapMaxX = 100;
    private class FindMAP
        {
            private int[][][] map = new int[10][100][100];
            private int[][] BlockStruct = new int[100][3];
        }
        FindMAP tMap = new FindMAP();
    I want to use:
    Java Code:
    private int[][] map = new int [10][10000];
    so I can remove the ConvertXY function as I hear having more elaborate arrays are slower. int[] is faster than int[][] ect. I came from programming for the PC where the minor increase in speed wasn't ever noticeable so it was always over looked.

    http://pastebin.com/6DVehSdW
    is the pastebin I created
    Last edited by 0circle0; 07-07-2011 at 03:36 AM.

  6. #6
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,931
    Rep Power
    19

    Default

    So.
    What is all this stuff?
    I've done A* before, but I don't entirely recognise how you've done it, and especially what everything all your variables are.
    I'm asking because, and I know this can't be right, it looks to me like you're looping through every square in your map each time in FindLowestF.

  7. #7
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    This is the first time I have done A*. FindLowestF just looks at each square on the open list and finds the one with the lowest F Value. G+H. I may have to try using a vector again and making my own sort function since Java-me doesn't have that feature. At the time I thought a vector was automatically sorted, apparently it isn't, which would be why I never saw any speed increase.

    FindLowestF searches the MAPOpenList and records the lowest F Value.
    FindLowestF is called by CheckNext which then closes that current square and opens the Squares next to it skipping those on the closed list.
    Some of the functions are for drawing the path to the MAPNumber and have no impact on the algorithm at all. Functions MakeTurn, DefinePath, and DrawPath are called only one time ever and are not used by the algorithm except to put the path into the map.

    Most of the variables like ...Time and ...OldTime are just used to time each function as this is another feature, at least with the GUI I am using, that Java-Me doesn't have. Some variables are not used yet. And the rest are used by MIDP for mobile devices( Sprite/Image ). I just pastebinned the Canvas class.

    I'll put the vector back in to keep track of the open list instead of storing it in an array, and just create a function to sort the vector. Which should be quick if I keep track of how many Squares I open and then only sort those that are added to the list, instead of sorting the entire thing every time. Will post back after the first test as to what I changed to make sure I am using vector correctly as I have never used vector in any language before.
    Last edited by 0circle0; 07-06-2011 at 03:04 PM.

  8. #8
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,931
    Rep Power
    19

    Default

    But that doesn't look like looping through the open list to me.
    It looks like looping through all squares on the map...or am I misreading the variables here?

    Isn't the open list a list of current potential routes, not a list of all unchecked squares?

  9. #9
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    EDIT:I think I may see what you mean. map is the entire array, including Open and Close lists F G and H values the Map itself and the Objects placed on the map which is stored into
    Java Code:
    int[][][] map = new map[10][100][100]
    Java Code:
    private final int MAPNumber = 0, MAPObjects = 1, MAPCollide = 2, MAPGValue = 3;
        private final int MAPHValue = 4, MAPFValue = 5, MAPOpenList = 6, MAPClosedList = 7, MAPParentList = 8;
    The Open List is in an Array, 100x100 Each block represents if the block is open.
    Java Code:
    for (y = 0; y < MapMaxY; y++)
                    for (x = 0; x < MapMaxX; x++)
                        if (MainVar.map[MAPOpenList][y][x] == 1) //[B]This XY Location is Open[/B]
                            if (MainVar.map[MAPFValue][y][x] < Lowest)
                            {
                                FoundOpen = 1;
                                Lowest = MainVar.map[MAPFValue][y][x];
                                NextToCheck = y * MapMaxX + x;
                            }
    There a better way of doing it? I tried vector again, but even unsorted and not even using the vector just putting elements in and taking them out made the time to execute explode. removeElement is very slow and removes the option of even using a vector, perhaps I can sort the MAPOpenList Array and take which ever one is at map[MAPOpenList][0][0]. or Create an OpenList array separate from the map array in the FindMAP class and sort that as a int[] instead of int[][][] how it is now. or just sort the vector from highest to lowest and remove the lastElement rather than firstElement.
    Last edited by 0circle0; 07-06-2011 at 05:15 PM.

  10. #10
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,931
    Rep Power
    19

    Default

    Except at the start you have precisely one item in the open set...that is the start square.
    And yet it looks to me (and I haven't looked really closely here, I am at work after all) that you are still checking all 10000 squares.

    That's an incorrect interpretation of A*.

    The open set is current potential paths (with an open node, that is a node with potential to go somewhere). So you should be going through your open nodes looking for the one that has the cheapest values.

  11. #11
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    Yes, that only happens the first time, I should change that to make FoundOpen = 1 and NextToCheck = StartY * MapMaxX + StartX. I understand what you are talking about, I should have an array for just the open nodes and search that rather than search every square. That would increase the speed a lot I would imagine and go from searching all 10000 to only having to search at most a few hundred assuming worst case scenario.
    Last edited by 0circle0; 07-06-2011 at 05:51 PM.

  12. #12
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,931
    Rep Power
    19

    Default

    That's the way it normally works.
    You store the open nodes, with their "score" (current cost plus estimated cost to destination).
    So you start with 1, then 4 (or 8 if you allow diagonals), assuming no blocking terrain, and so on.
    You should be able to code a way to insert the newly tested nodes into their correct position in an ordered array as well, thus allowing you to simply pick the one at the head. That ought to cut down the amount of checking even further.

  13. #13
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    Doing that right now. Just have to change some code around. Work 3rd shift so I may have to finish later tonight or tomorrow. Depending on how this compile goes.

    Keep getting array out of bounds Exception

    EDIT:
    Well I did it. Here are the new results from the Mobile Device, these also include having system.currentTimeMillis() in every function, which taking these out the numbers will be a lot lower.
    Java Code:
    StartPathFinding: called 1 time took 9,046 ms from 99,489ms (9 seconds down from 1 min 39.4 seconds) to execute
    CheckNext: called 5,539 times took 4,154ms from 1,429ms (4.1 seconds up from 1.4 second) to execute
    ConvertXY: called 0 times took 0ms (.000 seconds) to execute due to this function is no longer available
    FindLowestF: called 5,539 times took 310ms from 97,897ms (.3 seconds down from 1 min 37.8 seconds) to execute
    DrawPath: called 1 time took 4ms (.004 seconds down from .009 seconds) to execute
    DefinePath: called 1 time took 9ms (.009 seconds down from .023 seconds) to execute
    MakeTurn: called 144 times took 5ms (.005 seconds at no change from .005 seconds) to execute
    Start: called 1 time took 88ms (.088 seconds up from .083 seconds) to execute
    CreateClosedList: called 1 time took 88ms (.088 seconds up from .083 seconds) to execute
    Close: called 5,339 times took 850ms (.85 seconds up from .036 seconds) to execute
    CheckBounds: called 22,156 times took 140ms (.140 seconds up from .063 seconds) to execute
    CheckLists: called 22,156 times took 2,178ms (2.178 seconds up from .177 seconds) to execute
    Open: called 5,614 times took 423ms (.423 seconds down from .629 Seconds) to execute
    SetParent: called 5,615 times took 55ms (.055 seconds up from .051 seconds) to execute
    DefineGHF: called 5,614 times took 229ms (.229 seconds down from .36 seconds) to execute
    FindOrigin: called 5,614 times took 70ms (.07 seconds down from .104 seconds) to execute
    FindDestination: called 5,614 times took 41ms (.041 seconds down from .065 seconds) to execute
    ClearALL: called 0 times took 0ms (0 seconds) to execute
    FindLowestF was skipped 1,189 times saving 849ms (.849 seconds)
    If I take out all the timers except the StartPathFinding one
    Java Code:
    StartPathFinding: called 1 time took 8,400 ms from 99,489ms (8.4 seconds down from 1 min 39.4 seconds) to execute
    That is a significant increase in speed. Though you can see some function increased a great deal, most noticeable is CheckLists and Close, will have to figure out why those two functions decided to increase dramatically.
    Last edited by 0circle0; 07-06-2011 at 11:35 PM.

  14. #14
    0circle0 is offline Member
    Join Date
    Jul 2011
    Posts
    18
    Rep Power
    0

    Default

    Only problem now is that the path isn't drawn correctly. There are gaps

    Something new I have to figure out now. At least it is faster. Thanks a lot for the help.

    EDIT: Found the problem and fixed it.
    Last edited by 0circle0; 07-07-2011 at 12:58 AM.

Similar Threads

  1. How to make my download class faster
    By pietertje in forum New To Java
    Replies: 3
    Last Post: 08-07-2010, 11:19 AM
  2. * Help: Java Code For Cpu Scheduling Algorithm
    By coldvoice05 in forum AWT / Swing
    Replies: 2
    Last Post: 03-10-2010, 03:43 PM
  3. * Help: Java Code For Cpu Scheduling Algorithm
    By coldvoice05 in forum New To Java
    Replies: 1
    Last Post: 07-15-2009, 04:30 AM
  4. Help with Algorithm to the code!
    By sfe23 in forum New To Java
    Replies: 1
    Last Post: 03-03-2009, 12:17 AM

Tags for this Thread

Posting Permissions

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