Fixing PathFinder::aStar()

[hailstone]

I've done a quick test with 0.2.11 and the pathfinder branch by creating lots of initiates and getting them all to mine the same gold. In 0.2.11 it would start to lock up after about 7 initiates. With the new pathfinding there were no lockups. The only problem I found was when moving a unit to the corner it goes in the opposite direction.

Could you provide instructions for compiling with the path textures?

When you're ready to merge with trunk I'll take a closer look at the source. I think the code style should be more like the other Glest code but since we have no coding standard in place this is up for discussion.

What do you think of using an online code review tool?

[silnarm]

The only problem I found was when moving a unit to the corner it goes in the opposite direction.

I had some issues with units heading off in the wrong direction a few times, thought I'd cleared that all up, but obviously not

Could you provide instructions for compiling with the path textures?

There are some defines at the top of pathfinder.h for timing and logging various things, but most of them aren't hooked up anymore, only PATHFINDER_TIMING still works now.  For the map metrics and paths you need PATHFINDER_DEBUG_TEXTURES, I couldn't find a good spot to put this in a header, as it's needed in various places that otherwise have nothing to do with each other (ie, primarily the PathFinder and the Renderer), so it's easiest to define it on the command line. You will of course also need,
http://www.mediafire.com/download.php?z242om2eunt
plonk them in data/core/misc_textures [I guess these should actually be in the repository...]

I think the code style should be more like the other Glest code but since we have no coding standard in place this is up for discussion.

I suppose it makes sense to have the code look alike, although it is nice to be able to tell who wrote what just by looking at the code. Daniel's code certainly looks similar to Martino's, but you can tell Daniel is little (only a little) more liberal with his use of whitespace... If you've looked at my code you'll be aware I'm a big fan of the space bar.
I'm not to fussed about it myself, I can set VC++ up to reformat all my code before I commit if you like, but I can't write code like that Fairly set in my ways when it comes to brace positioning and such.

What do you think of using an online code review tool?

Certainly a good idea, but do we have the numbers to make it work?

[silnarm]

Apologies, the debug textures were set up to show the forward and backward paths, which would have only been happening when start and destination were at least 15 cells apart.

I've changed it to show the end path...

The weird behaviour when pathing to the south or east edges of the map remains, I'll try to sort that one out on the weekend, pathing to the west or north edge was seg faulting, that one's been fixed.

Edit: ...and I've changed the game project file to link with zdll.lib, rather than zlib.lib

Edit2: south and east edge bug found and squashed...  looks like I might be able to start looking at the whole shipyard/dock thing on the weekend

[silnarm]

Recently discovered Glest's A* is not A* at all, but a 'greedy best first search'. I've implemented a proper A* and optimised it to the best of my ability... I'm happy with the running time, but haven't tested it extensively yet. I think for the next GAE I'll make it an option to use either the greedy algorithm or A*.

The right Heuristic...
I spent plenty of time reading Amit Patel's pages on A*, and I'm confident that it's pretty much as fast as it can be.  The heuristic needed to be changed though, the euclidean distance that was being used causes problems with proper A* on a grid, because it lies about the true distance to a goal node. At 45 degree angles things look fine, but in between it underestimates and causes A* to expand nodes closer to the start...

Shown here, on the left, is the old heuristic on a path at a roughly 22.5 degree angle, the Yellow nodes are the 'frontier' of the search (the open list), the red nodes are the expanded nodes (the closed list).  Expanding nodes is a relatively expensive operation.  Shown on the right is a similar path, calculated with the same algorithm, but with a 'diagonal distance' heuristic, the 'correct' one for us... note that (in this case) every expanded node ended up on the path, it's as fast as the greedy search when obstacles are not present....



Note that this heuristic is still admissible (at least until we add some more interesting terrain types) so the search will still find the optimal path, it just won't 'fan out' if it doesn't need to...

[Omega]

Wow, having seen A* pathingfinding quite a bit, that is pretty good. However, I would like to see an image or two of how the pathfinding is when going through a maze. It might lead to making the pathfinding in mazes better if we can see how they will react. As well, I am curious how the units will move exactly in crowds of units. Would you be able to upload a build (win32) of your modified engine for the pathfinding, which shows the pathfinding like that? I really would like to test some things!

[assassin]

You can get the source from the svn...

[Omega]

I'd prefer a prebuild, and besides, I can't figure out which I am looking for. I want the one that is used for the pathfinding shown above...

[silnarm]

Wow, having seen A* pathingfinding quite a bit, that is pretty good. However, I would like to see an image or two of how the pathfinding is when going through a maze. It might lead to making the pathfinding in mazes better if we can see how they will react.

Well, Proper A* will find the optimal path... Our A* does of course have a node limit in built.  If this is exceeded, all bets are off.  At the moment I handle this by simply picking the node closest the goal, and then 'backing up' a bit, in case that happens to be in a cul-de-sac. When this 'temporary destination' is reached, a new path is calculated.

The node limit with mazes probably wont work so well, it will almost certainly expand many nodes trying to go around... if you limited such opportunities (with a very 'packed' map) then it would come down to whether the node limit was hit or not... if so it will pick the closest node and backoff a few steps... unlikely to be very effective in a maze.

eg. I had to increase the node limit to 4096 (probably too high for regular in game use) to get through this...


Of course, once we go hierarchical, even with the node limit, it will handle this with ease

As well, I am curious how the units will move exactly in crowds of units. Would you be able to upload a build (win32) of your modified engine for the pathfinding, which shows the pathfinding like that? I really would like to test some things!

Group movement is still an issue... I have been looking at options to make this more intelligent.  "Windowed Hierarchical Cooperative A*" (WHCA*) looked promising, but there are serious issues that would need to be solved to get it working 'in the wild'.  Also if I do run with that, I have to figure out how to make it work with Hierarchical Pathfinding A* (HPA*) [Actually, we'll be getting a variant, HAA*]

I have some ideas I'm going to play with after we get a new release out, to 'manage' resource areas and choke points on a per team basis... If that works well enough, maybe a 'proper' cooperative movement algorithm will not be needed.

I'd prefer a prebuild, and besides, I can't figure out which I am looking for. I want the one that is used for the pathfinding shown above...

I'll add options to switch algorithms and turn on/off timing and debug textures... binaries soon...

[hailstone]

I saw that you merged the pathfinder and the merge_3.2.2 branches. I would have thought it would be better to wait until it is cleaned and merged with trunk before doing anything else with it.

Also I don't know that it's a good idea to be refactoring in a branch for pathfinding especially since no automated tests are setup. I'm thinking that changes unrelated to pathfinder would make it harder to merge it with trunk later on, more so if other people are working on it at the same time and have made other changes to trunk.

It seems to be getting a lot more complex than the standard A* algorithm  . I still have a week until uni starts again so if you wanted me to do anything just let me know.

[silnarm]

I saw that you merged the pathfinder and the merge_3.2.2 branches. I would have thought it would be better to wait until it is cleaned and merged with trunk before doing anything else with it.

I merged fixes from trunk as well... the pathfinder branch is up to date with everything except the tinyxml branch.

Also I don't know that it's a good idea to be refactoring in a branch for pathfinding especially since no automated tests are setup. I'm thinking that changes unrelated to pathfinder would make it harder to merge it with trunk later on, more so if other people are working on it at the same time and have made other changes to trunk.

Yes... yes, yes... but no one else is working on it, I was getting concerned with all the branches and I wanted it 'all in one place', I also want to add things to the engine, and that means refactoring bloated objects that probably shouldn't actually exist anyway. I didn't want to do it in trunk without OK-ing it with you, it's your show... so as I mentioned in the refactoring topic, if you're happy with the changes we can just copy it back to trunk...

It seems to be getting a lot more complex than the standard A* algorithm  . I still have a week until uni starts again so if you wanted me to do anything just let me know.

Fairly standard
I've just extended the 'range' of 'local annotations' (so when calculating a path, unit's within two cells are considered) and the results look pretty nice, groups don't seem to mind 'spreading out' ... I think the combination of this extended range and the new heuristic is helping out here...

[hailstone]

Sorry I completely missed that topic. I was worried that it might get out of hand. Just me being paranoid I think. 

I compiled and ran the updated pathfinder branch and it's not running as smooth as it was before. I don't think it is because of changes though because an older version of it is doing the same thing even though it was working before. There are no frame rate drops just a regular brief pause every second. The other possibility could be that I didn't notice it before because it is a huge improvement on the previous lag.

[silnarm]

I compiled and ran the updated pathfinder branch and it's not running as smooth as it was before. I don't think it is because of changes though because an older version of it is doing the same thing even though it was working before. There are no frame rate drops just a regular brief pause every second. The other possibility could be that I didn't notice it before because it is a huge improvement on the previous lag.

Hmmm... that's curious.. it runs smooth for me.

I did notice that somehow in release build the 'Game' is always calling checkWinnerScripted(), even when not playing a scenario... But it works fine in debug build...

I'll do some more testing...

[silnarm]

I'm about to fix a bug I've fixed before... a couple of times actually.

Also I don't know that it's a good idea to be refactoring in a branch for pathfinding ...

For the record, I'm an idiot  and hailstone is wise beyond his years.

[Omega]

Maybe by your harsh standards, but to me, you're a genius!