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.

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;

}