Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pathfinder  (Read 4448 times)
0 Members and 1 Guest are viewing this topic.
Offline Xyle
« Posted 2009-11-30 05:14:03 »

Wanted to post my new pathfinding applet and let people play with it. It uses A* and its a almost a port of the code I did in Blitz3d a year or so ago. The java version came out much cleaner and more efficient, of course the Java version is 2d where the Blitz version was for 3d. Try it out and let me know what you think.

It would be great if someone can compare the timing to their own pathfinding algo's out there, the timing is purely the time it takes from starting the pathfinding to finishing the search, no drawing or rendering is involved in the timing.

Let me know what you think!
Make sure you click inside the applet to capture the focus.
Press the 6 button to throw random blocks throughout the map
left click a cell to make it the start cell, turns blue
left click again to make selected cell the target cell, turns red
Right click the mouse anywhere in the applet to find the path.

You can use the middle mouse button to create a new block or erase a block

PathFinder Applet

Heres a screen shot...

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline CommanderKeith
« Reply #1 - Posted 2009-11-30 15:58:31 »

Pretty cool, I like path finding a lot too. Have you tried many optimisiations? I found that the binary heap was a massive performance boost.

This site has some good speed tips and a link about binary heaps at the bottom: http://www.policyalmanac.org/games/aStarTutorial.htm

Offline harima555

Junior Newbie





« Reply #2 - Posted 2009-11-30 17:09:09 »

tried it, played whit it , kools nice!!!!
tried a lot or diferent scenarios..labrynts?
very responsive =)
keep up the good work.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline pjt33
« Reply #3 - Posted 2009-11-30 19:24:49 »

Pretty cool, I like path finding a lot too. Have you tried many optimisiations? I found that the binary heap was a massive performance boost.
Shocked Why would anyone implement A* and not use a heap at least as sophisticated as a binary heap?

Xyle, if you want to get useful comparisons then you're going to have to post your source code. You're also going to have to look at larger test cases - a 16ms test is far too small to measure real differences unless the one you're measuring against is at least an order of magnitude slower. As a general rule of thumb I would say that a performance test which doesn't run for at least a minute won't give you any useful information.
Offline appel

JGO Wizard


Medals: 68
Projects: 4


I always win!


« Reply #4 - Posted 2009-11-30 23:01:24 »

Back at university I did an independent research project into pathfinding algorithms, implementation and optimization.

Well, here's my code, and it's executable using bat files (so beware!).

It's essentially an analyzing tool, to help visualize how the pathfinders works. The A* implementation supports multiple "storages" for the open and closed lists, and also different heuristics.

http://gamadu.com/temp/Pathfinder.zip


Few things you can do in that application:
- You can resize the grid by using arrow keys (WARNING, don't exceed 256x256...starts to lag)
- You can toggle on/off the gridlines using G
- You can move grid grid using W,A,S,D (buggy though)
- You can zoom in/out using + and - on the numkeypad.
- You can change the heuristics by pressing 1-5 on the qwerty-keypad (only in A*)
- You can press SPACEBAR to show how the nodes were traversed (pink show paths tried, fading to black means not tried as much)
- You can reset the view of the grid by pressing R.
- Press enter to relocate the start and goal nodes (sorry, you can't manually position them yet!)
- Press F5 to refresh the pathfinding operation... nice to do a few times to see the timer.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Xyle
« Reply #5 - Posted 2009-12-01 01:54:35 »

Awesome! Thanks for the responses. Glad a some people found it entertaining.


You can check out the source code here. Its a zip file that includes the classes, java file and the .htm file. Its hosted on Filefront so it should be there for a while. Get it here!

As for
Shocked Why would anyone implement A* and not use a heap at least as sophisticated as a binary heap?

Hehehe, I've never used them before and haven't looked at them, but since CommaderKeith recommended it, I will definitely look into it.

I really appreciate the feedback and the responses. Thank you!

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline CommanderKeith
« Reply #6 - Posted 2009-12-01 02:27:13 »

Shocked Why would anyone implement A* and not use a heap at least as sophisticated as a binary heap?


What's better than a binary heap?

Offline Xyle
« Reply #7 - Posted 2009-12-01 02:40:08 »

Appel, I really appreciate the sharing of your code. I changed my timing to match yours and ran a few tests that matched the map up with yours. I was excited to see that the paths found were identical and the search paths were relatively close for the most part. Although I was really bummed to see that your code is almost 3 times faster than mine, hahahaha!!

Now, who said what about Binary Heaps? lol, I'm going to have learn em I reckon!

heres the screenie...

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline appel

JGO Wizard


Medals: 68
Projects: 4


I always win!


« Reply #8 - Posted 2009-12-01 08:40:15 »

No problem Xyle. You can use it to study why it's so fast Wink

I probably made a bit more complex than it needed to be, in order to support multiple algorithms.

Also try out different heuristics by pressing 1 through 5 keys. I found that 4 is the fastest, but 5 produces the smoothest paths. You'll need to enlarge the map to see the difference.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline pjt33
« Reply #9 - Posted 2009-12-01 10:32:59 »

What's better than a binary heap?
There are hundreds of heaps in the literatures. AIUI Fibonacci heaps were designed specifically for use with Dijkstra's algorithm, and are asymptotically better; relaxed heaps are also asymptotically better, and I'm sure many others are too. Then there are things like the C algorithm which can be seen as an algorithmic variant of A* or as A* with a variant heap. I use it with a non-admissible heuristic where I care about finding a route quickly more than finding the best route.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #10 - Posted 2009-12-01 11:19:42 »

Cool, thanks for the info, that's very interesting. What are you making with your path finding algorithm? An RTS?

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #11 - Posted 2009-12-01 15:44:17 »

Appel, I really appreciate the sharing of your code. I changed my timing to match yours and ran a few tests that matched the map up with yours. I was excited to see that the paths found were identical and the search paths were relatively close for the most part. Although I was really bummed to see that your code is almost 3 times faster than mine, hahahaha!!

Now, who said what about Binary Heaps? lol, I'm going to have learn em I reckon!

heres the screenie...
Hm, you definitely need some optimization here, yeah. Actually, you might even have done something wrong. I've got a maze app I wrote that solves random mazes more or less instantly, even if they're fairly enormous. I've also got an algorithm on the iPhone that can solve situations comparable to the one you posted in less than a second... that's with a mobile processor. It's weird that such a small area is taking you 3 seconds to solve.

The maze app I wrote does not really use any optimizations like using binary heaps, but the one on the phone uses a HashMap equivalent for faster lookup. Actually you can have a look at my maze app, it's open source.
http://www.otcsw.com/maze.php

See my work:
OTC Software
Offline pjt33
« Reply #12 - Posted 2009-12-01 17:34:32 »

Cool, thanks for the info, that's very interesting. What are you making with your path finding algorithm? An RTS?
Technically yes, although it's not exactly what most people think of when they hear RTS. It's an alternative history strategy game.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2009-12-01 17:51:57 »

I'd love the completely different approach: not calculating but finding your path.

http://www.red3d.com/cwr/steer/
http://www.red3d.com/cwr/steer/Obstacle.html
http://www.red3d.com/cwr/steer/CrowdPath.html
http://www.red3d.com/cwr/steer/Unaligned.html

There is a high chance you can find most targets without encountering obstructions. Of there are obstructions, just let A* create a very rough path, and 'feel' your way from target to target. This is very realistically looking for crowds and group movement.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #14 - Posted 2009-12-01 19:47:16 »

I'd love the completely different approach: not calculating but finding your path.

http://www.red3d.com/cwr/steer/
http://www.red3d.com/cwr/steer/Obstacle.html
http://www.red3d.com/cwr/steer/CrowdPath.html
http://www.red3d.com/cwr/steer/Unaligned.html

There is a high chance you can find most targets without encountering obstructions. Of there are obstructions, just let A* create a very rough path, and 'feel' your way from target to target. This is very realistically looking for crowds and group movement.
That's very cool. I would actually use that approach if I hadn't already written A*. But I find myself spending lots and lots of time trying to tweak A* to look more natural, especially when diagonal movements are allowed in a grid-based environment.

See my work:
OTC Software
Offline Jono
« Reply #15 - Posted 2009-12-01 21:08:07 »

There are hundreds of heaps in the literatures. AIUI Fibonacci heaps were designed specifically for use with Dijkstra's algorithm, and are asymptotically better; relaxed heaps are also asymptotically better, and I'm sure many others are too. Then there are things like the C algorithm which can be seen as an algorithmic variant of A* or as A* with a variant heap. I use it with a non-admissible heuristic where I care about finding a route quickly more than finding the best route.
Just adding to this. In the maze examples there's no variation in move cost, so your heuristic will be "too good" and you won't be testing every aspect of the priority queues. One big advantage of Fibonacci heaps, pairing heaps etc. is improvement in decrease_key running time. If the heuristic can perfectly judge the distance to the goal when no obstacles exist, then there should never be duplicates in the open list that need updating, and decrease_key won't have to be used.

I guess it all comes back to making sure you are testing for exactly the situation you'll be using them in... reviled micro-benchmarks and so on.
Offline Xyle
« Reply #16 - Posted 2009-12-02 03:12:45 »

I've also got an algorithm on the iPhone that can solve situations comparable to the one you posted in less than a second... that's with a mobile processor. It's weird that such a small area is taking you 3 seconds to solve. "

Thanks for the looky! Those are millisecs, not seconds. I was thinking 3 millisecs was pretty fast considering that it could do that same routine 300 more times before getting even close to 1 second. Hahahaha. Until I saw Appels that is.

I am thinking that main slowdown is when I gather and set all the neighbor cells. It takes 6 checks to make sure each neighbor cell is valid, than it sets each cell's f,g,h and parent values. It must do this 8 times for each cell that gets checked on the openlist to determine if the cell is valid and should be put on the openlist. This was the main problem in my code that took me a day to figure out. I dont think it can be broke, I tested it many many times on blocked targets and inaccessible targets, plus different size maps, etc. I cant think of any other way of checking and setting the neighbor cells. Ive looked through tons and tons of examples and source but cant really get a grip on how other people do it.

Heres the code that checks and sets the neighbor cells, topleft, top, topright, left, right, bottomleft, bottom, and bottomright cells of current cell being checked...

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
//Add adjacent squares to the openlist unless they are already there
//or they are on the closed list
//If they are already on the open list, supposed to check them for a better path
//TopLeft Cell
int celNum = currCell-(mapRow+1);
int totCells = mapRow*mapCol;
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row-1 && cell[celNum].col == cell[currCell].col-1){
      if(cell[celNum].listType == 0){
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("1Checked topleft cell "+celNum);
      }
   }
}
//TopCell
celNum = currCell-(mapRow);
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row-1 &&cell[celNum].col == cell[currCell].col){
      if(cell[celNum].listType == 0){  
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+10;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("2Checked top cell "+celNum);
      }
   }
}
//TopRight Cell
celNum = currCell-(mapRow-1);
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row-1 &&cell[celNum].col == cell[currCell].col+1){
      if(cell[celNum].listType == 0){  
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("3Checked topright cell "+celNum);
      }
   }
}
//Left Cell
celNum = currCell-1;
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row &&cell[celNum].col == cell[currCell].col-1){
      if(cell[celNum].listType == 0){  
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+10;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("4Checked left cell "+celNum);
      }
   }
}
//Right Cell
celNum = currCell+1;
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row &&cell[celNum].col == cell[currCell].col+1){
      if(cell[celNum].listType == 0){  
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+10;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("5Checked right cell "+celNum);
      }
   }
}
//BottomLeft Cell
celNum = currCell+(mapRow-1);
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row+1 && cell[celNum].col == cell[currCell].col-1){
      if(cell[celNum].listType == 0){
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("6Checked Bottomleft cell "+celNum);
      }
   }
}
//Bottom Cell
celNum = currCell+(mapRow);
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row+1 &&cell[celNum].col == cell[currCell].col){
      if(cell[celNum].listType == 0){
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+10;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("7Checked bottom cell "+celNum);
      }
   }
}
//BottomRight Cell
celNum = currCell+(mapRow+1);
if(celNum > -1 && celNum < totCells && cell[celNum].block == 0){
   if(cell[celNum].row == cell[currCell].row+1 &&cell[celNum].col == cell[currCell].col+1){
      if(cell[celNum].listType == 0){
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("8Checked bottomright cell "+celNum);
      }
   }
}


If anyone sees anything that could help speed this up, it would be greatly appreciated. As I said, Ive looked at others codes and tried chasing down this step, but it seems to be elluding me.

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline CommanderKeith
« Reply #17 - Posted 2009-12-02 05:09:05 »

Just adding to this. In the maze examples there's no variation in move cost, so your heuristic will be "too good" and you won't be testing every aspect of the priority queues. One big advantage of Fibonacci heaps, pairing heaps etc. is improvement in decrease_key running time. If the heuristic can perfectly judge the distance to the goal when no obstacles exist, then there should never be duplicates in the open list that need updating, and decrease_key won't have to be used.

I guess it all comes back to making sure you are testing for exactly the situation you'll be using them in... reviled micro-benchmarks and so on.

Hi Jono, what's an example of this? I don't understand what you're saying. Do you mean that in some simulations the heuristic changes as you find out more info, so the heap needs re-ordering?

I'd love the completely different approach: not calculating but finding your path.

http://www.red3d.com/cwr/steer/
http://www.red3d.com/cwr/steer/Obstacle.html
http://www.red3d.com/cwr/steer/CrowdPath.html
http://www.red3d.com/cwr/steer/Unaligned.html

There is a high chance you can find most targets without encountering obstructions. Of there are obstructions, just let A* create a very rough path, and 'feel' your way from target to target. This is very realistically looking for crowds and group movement.
That's cool, great applet examples. Looks like the best way to achieve unit avoidance.

Offline raft

Senior Newbie




aptalkarga.com


« Reply #18 - Posted 2009-12-02 08:57:12 »

3 milliseconds is good but it could be better. on such a tiny grid, the result should be almost instantaneous.

have a look at this pathfinder. it's in JavaScript but does almast equally well in small portions of grid. in chrome it runs even faster. chrome's JS engine perform really good btw..

Offline pjt33
« Reply #19 - Posted 2009-12-02 09:05:07 »

Xyle, your code doesn't actually look correct.

Firstly, a handy tip for reducing the size of the code: remember rotation matrices?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
for (int diag = 0; diag < 2; diag++) // 0: not diagonal; 1: diagonal
{
    int edgeCost = 10 + diag * 4;
    int dx = 1;
    int dy = diag;
    for (int i = 0; i < 4; i++)
    {
        update(x+dx, y+dy);
        int t = dx;
        dx = dy;
        dy = -t;
    }
}

All 8 cases handled. If you don't do diagonals you can ditch the outer loop.

Secondly, the actual processing code. You have (taking top-left for example)
1  
2  
3  
4  
5  
6  
7  
8  
      if(cell[celNum].listType == 0){ 
         addOpenList(celNum);
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
         //System.out.println("1Checked topleft cell "+celNum);
      }

Shouldn't that be as follows?
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
      if(cell[celNum].listType == 0){ 
         addOpenList(celNum);
      }
      if (cell[currCell].gVal+14 < cell[celNum].gval)
      {
         cell[celNum].gVal = cell[currCell].gVal+14;
         cell[celNum].hVal = findDistance(celNum,tCell);
         cell[celNum].fVal = cell[celNum].gVal+cell[celNum].hVal;
         cell[celNum].parent = currCell; //Make currCell the parent of adjacent cells
      }

Assuming that gVal is initialised to Integer.MAX_VALUE / 2. Since you're assigning a greater cost to diagonal movement than to horizontal movement your screenshot in the first post is quite clearly showing a non-optimal route, and I'm pretty sure that the reason is that you're never reducing the key of a cell in the open list.
Offline Jono
« Reply #20 - Posted 2009-12-02 20:28:42 »

Quote from: pjt33
Since you're assigning a greater cost to diagonal movement than to horizontal movement your screenshot in the first post is quite clearly showing a non-optimal route, and I'm pretty sure that the reason is that you're never reducing the key of a cell in the open list.
I think that's ok - the diagonal moves actually are slightly cheaper: 14 cost instead of 10*sqrt(2) cost. Edit: I see what you mean now down the bottom right of the map. Hmm.. wven without reducing the key shouldn't this still work?  Undecided Something wrong with the priority queue?
Edit2: I can't access the files anymore. Is it using manhattan distance heuristic (overestimating cost) instead of Euclidean distance? That could explain it.

Hi Jono, what's an example of this? I don't understand what you're saying. Do you mean that in some simulations the heuristic changes as you find out more info, so the heap needs re-ordering?
Yeah, I wasn't very clear. When you add a neighbour to the open list, it may already be in there but with different f-value. This will happen pretty frequently in grid-based search. There are two ways of handling it:

1) Just add neighbours to the list and don't worry about it. The priority queue will sort them so the best one is used first. Downside: if there are lots of duplicate neighbours, the open list will be much larger, slowing each operation.

2) Find the duplicate in the open list (usually via an extra hashtable), and compare the two f-values. If the f-value of the new neighbour is lower, you want to have it in the open list instead. Removing the old one and adding the new one is a duplication of effort. Instead you can update the existing node in the open list (including changing its f-value) and have the priority queue resort itself. This is the decrease_key operation (decreases the f-value).

Binary heaps have reasonably inefficient decrease_key operations (still log(n) though). Fancier heaps like Fibonacci heaps are more efficient. The problem is that when the amount the heuristic decreases after one step is equal to the cost for the move added to the g-value, a neighbour that is already on the open list will never have a lower f-value, and decrease_key won't need to be used.

In the grid example here it's not quite the case, but it is close enough that I think there will still very rarely be duplicates that need updating. If the cost to move between grid squares is different in different locations (like in any game with variable terrain), then this should turn up a lot more.
Offline pjt33
« Reply #21 - Posted 2009-12-02 23:23:32 »

I see what you mean now down the bottom right of the map. Hmm.. wven without reducing the key shouldn't this still work?
Hmm. You have a point there. It should be incorrect, but the specific problem observed in the screenshot shouldn't happen if the priority queue is working. The actual result looks like pure breadth-first search.
Offline Xyle
« Reply #22 - Posted 2009-12-03 02:35:11 »

Raft,
I really, really appreciate you sharing that. I made a map 50x50 with random blocks spread throughout and did the same starting points, opposing corners and this is what I showed...



Your Javascript page showed the path found in 74 MS on a comparable map with 30 rows x 50 cols.

Of course I am pretty happy with that. I really appreciate it.


PJT33,
Most of the stuff your saying is way above my head. Rotation Matrices? I've never seen or heard of em. I still havent grasped Binary heaps. I will have to reread what you posted a few times to try to understand it. I really appreciate the tips, it just may take a while to sink in and try to institute.

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline CommanderKeith
« Reply #23 - Posted 2009-12-03 05:11:31 »


Yeah, I wasn't very clear. When you add a neighbour to the open list, it may already be in there but with different f-value. This will happen pretty frequently in grid-based search. There are two ways of handling it:

1) Just add neighbours to the list and don't worry about it. The priority queue will sort them so the best one is used first. Downside: if there are lots of duplicate neighbours, the open list will be much larger, slowing each operation.

2) Find the duplicate in the open list (usually via an extra hashtable), and compare the two f-values. If the f-value of the new neighbour is lower, you want to have it in the open list instead. Removing the old one and adding the new one is a duplication of effort. Instead you can update the existing node in the open list (including changing its f-value) and have the priority queue resort itself. This is the decrease_key operation (decreases the f-value).

Binary heaps have reasonably inefficient decrease_key operations (still log(n) though). Fancier heaps like Fibonacci heaps are more efficient. The problem is that when the amount the heuristic decreases after one step is equal to the cost for the move added to the g-value, a neighbour that is already on the open list will never have a lower f-value, and decrease_key won't need to be used.

In the grid example here it's not quite the case, but it is close enough that I think there will still very rarely be duplicates that need updating. If the cost to move between grid squares is different in different locations (like in any game with variable terrain), then this should turn up a lot more.

Thanks a lot for the explanation, pretty in-depth stuff. I think I understand what you mean. In my mesh-based A* path finder (http://www.java-gaming.org/topics/a-pathfinding-through-2d-polygons/19539/view.html) you must be referring to the percolateUp call on the last line of this code block:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
// add reachable nodes to the openList if they're not already there.
for (int i = 0; i < currentNode.getReachableNodes().size(); i++){
   KNode reachableNode = currentNode.getReachableNodes().get(i);
   if (closedList.get(reachableNode) == null){
      //if (openList.contains(reachableNode) == false){
      if (openMap.get(reachableNode) == null){
         reachableNode.setParent(currentNode);
         reachableNode.calcHCost(endNode);
         reachableNode.calcGCost();
         openList.add(reachableNode);
         openMap.put(reachableNode, reachableNode);
      }else{
         assert reachableNode.getGCost() != reachableNode.G_COST_NOT_CALCULATED_FLAG;
         double currentGCost = reachableNode.getGCost();
         double newGCost = currentNode.getGCost() + currentNode.getPoint().distance(reachableNode.getPoint());
         if (newGCost < currentGCost){
            reachableNode.setParent(currentNode);
            reachableNode.calcGCost();
            // Since the g-cost of the node has changed,
            // must re-sort the list to reflect this.
            int index = openList.indexOf(reachableNode);
            openList.percolateUp(index);
         }
      }
   }
}


I haven't found that this method takes much CPU time yet, but when it does I'll know it's time to swap the BinaryHeap for a Fibonacci heap. Thanks Jono Smiley

Offline raft

Senior Newbie




aptalkarga.com


« Reply #24 - Posted 2009-12-04 00:12:13 »

I really, really appreciate you sharing that.
np, it's a just a demo Grin

Your Javascript page showed the path found in 74 MS on a comparable map with 30 rows x 50 cols.
interesting, it obviously depends on browser and computer itself. on my old laptop, (ubuntu + firefox)  it's around 10-15 MS.

12 MS not bad, but i still think it can be better Wink

this is a java application running same demo. run it a few times to give JVM a chance to warm up. it runs 0-3 MS on my machine. the jar also contains the source code except AStar itself, which is JKilavuz's generic AStar implementation

r a f t

Offline Xyle
« Reply #25 - Posted 2009-12-04 03:01:10 »

I did show 12ms the first time, then 0 ms every time afterwards running the application. I'm sure it definitely depends on the browser and pc running the applets. Mine is a bit slow and outdated which is why I love attempting to develop things with it. Shouldn't have any problems with other people running them.

I do know that the way I find the adjacent cells and set their values is horribly unoptimized and causes major slowdowns, but until I understand what pjt33 eluded to, it will have to do. Of course I will keep poking and prodding at it til then, hehehe.

Thanks again for the insights.

Life is just a game, learn to play!
------------------------------------------
╬-YellzBellz Games!-╬ Cheesy
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #26 - Posted 2009-12-04 15:53:10 »

Thanks for the looky! Those are millisecs, not seconds. I was thinking 3 millisecs was pretty fast considering that it could do that same routine 300 more times before getting even close to 1 second. Hahahaha. Until I saw Appels that is.
Hahahaha, oh. Well that makes a lot more sense! I was wondering how you would manage to solve it so slowly. XD

See my work:
OTC Software
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (32 views)
2014-12-15 09:26:44

Mr.CodeIt (23 views)
2014-12-14 19:50:38

BurntPizza (50 views)
2014-12-09 22:41:13

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (58 views)
2014-11-29 21:32:03

toopeicgaming1999 (123 views)
2014-11-26 15:22:04

toopeicgaming1999 (114 views)
2014-11-26 15:20:36

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!