Fixing PathFinder::aStar()

[silnarm]

Greetings.
This topic is intended for the (technical) discussion of Glest's pathfinder, and specifically what's wrong with it and how to fix it.
I've been pulling Glest's implementation of the A* algorithm apart over the past few days, so I'll start this off with a very terse description of  “standard” A*, and then have a look at the A* in Glest, and see if anything is amiss...

Edit: 20-May-09
This contains a couple of small errors that I'm too lazy to fix.
Edit: 9-June-09
Ok, I've fixed them... and cleaned up the pseudocode.

Standard A*
For a standard issue A* we need a node structure with 4 pieces of information, the 'distance' to here, the 'heuristic' (estimated distance to destination), a 'vector' that points back to the (currently) best known node to get here from, and of course we need the map co-ordinates.
The other thing we need is a function to calculate the heuristic, we will just use, as Glest does, the 'Euclidean' distance to the destination (using trusty old Pythagoras).
Also, I'm ignoring the extra cost of moving diagonally, to keep things simple (as Glest also does).
With the node structure and heuristic function at hand and two initially empty lists, named Open and Cosed, the standard issue A* algorithm goes as such,

start with startPos and destPos // Our start position and destination position
set startNode.position to startPos
set startNode.heuristic to Euclidean distance from startPos to destPos
set startNode.distance to 0
add startNode to Open List
while Open List is not empty
  select node from Open List with lowest distance + heuristic
  // let's call it minNode
  if minNode is destination
    we found a path! (Follow the vectors back to start pos)
  else
    for each adjacent node // let's call it newNode
      if newNode is not on Closed List
        if newNode is on Open List
          if minNode.distance + 1 < newNode.distance
            set newNode.distance to minNode.distance + 1
            set newNode.vector to point at minNode
          else
            do nothing
        else if minNode->newNode is a legit move
          add newNode to Open List  // diag = sqrt(2)?
          set newNode.heuristic to manhatten distance to destination
          set newNode.distance to minNode.distance + 1 // diag = sqrt(2)?
          set newNode.vector to point at minNode
        else
          do nothing
      else
        do nothing
    //end for
    Remove minNode from Open List, add to Closed List
  // end if
//end while
If we get here, Open List is empty, Failure  

So, basically in each loop iteration we pick the 'best' node from the open list, this is the node with the smallest distance + heuristic. If this best node is the destination, we have found our path. Otherwise, we look at each of this nodes neighbours in turn, ignoring any on the closed list, possibly updating them if they're on the open list, and adding them to the open list otherwise.

Glest's A*
Glest's node structure looks somewhat different, the 'distance' to here is not stored, and as well as the vector pointing back (indicating the best known path to here) there is a 'forward' pointing vector. This forward pointing vector is only 'filled in' once the path has been found though, so it has been omitted from this description.
Glest's nodes also have a CellExplored member which I'm ignoring here, and the path finder has a node limit built in, which again, I'm ignoring... this is the 'bare bones' of the algorithm.

start with startPos and destPos // Our start position and destination position
set startNode.position to startPos
set startNode.heuristic to Euclidean distance from startPos to destPos
add startNode to Open List
while Open List is not empty
  select node from Open List with lowest heuristic
  // let's call it minNode
  if minNode is destination
    we found a path! (Follow the vectors back to start pos)
  else
    foreach adjacent node // newNode
      if newNode is not on Open or Closed List
      and minNode->newNode is a legit move
        add newNode to Open List  // diag = sqrt(2)?
        set newNode.heuristic to Euclidean distance to destination
        set newNode.previous to point at minNode
      else
        do nothing
    // end for
    Remove node from Open List, add to Closed List
  //end if
//end while
If we get here, Open List is empty, Failure  

As can been seen, it's a bit simpler than standard A*. With no 'distance to here' the best node at each step is simply the one with the lowest heuristic. Glest's version also doesn't consider nodes already on the open list, the standard version checks to see if the path to the (open) node is better through the current (best) node, and updates it if so. So Glest's A* may not find the optimal path, but it should execute much quicker.

OK, I think that should just about be enough for anyone to take in at once
I've made some further discoveries and tinkered a bit, and with a very simple optimisation I've managed to reduce the 'worst case' calculation time for a path to about a quarter of what it was.
I'll need to get 'clean' copy of numerous source files to make a patch, but I believe I can improve performance further with some not to drastic changes, so I'll try that out first.
For the moment, I need to take pause, and gather my thoughts
more soon...

[silnarm]

So, What is up with Glest's Path Finder?
The algorithm seems sound, so let's have a look at the implementation,
 here's the comments from inside the loop,
b1) is open nodes is empty => failed to find the path
b2) get the minimum heuristic node
b3) if minHeuristic is the finalNode, or the path is no more explored
   => path was found
b4) move this node from closedNodes to openNodes
and the inner loop (checking the neighbours),
//if node is not open and canMove then generate another node

Fairly straight forward, except of course b4 is the wrong way around, but the code is correct Of note are operations on both the Open and Closed lists and a call to minHeuristic(). In the inner loop (which is actually a loop in a loop in the code) our concern is the logical test in the if statement, containing calls to openPos() and map->aproxCanMove().
So we should have a look at minHeuristic(), openPos() and Map::approxCanMove() to see what they're doing... this is the route I initially took and has proved fruitful, using an Annotated A* we can eliminate the map->approxCanMove () call, which itself calls Map::isAproxFreeCell() at least once, three times if the move is diagonal. isAproxFreeCell() itself make further method calls, depending on certain conditions.
More on Annotated A* in a second... first...

What I didn't consider at first, possibly because it was hidden away in a typdef, was what data structure are we using for the open and closed lists???
The answer was most surprising...
   typedef vector<Node*> Nodes;
An STL Vector!!!
You know, the ones that are essentially arrays, that can dynamically grow as needed, by allocating new memory and copying the old contents to the new (bigger) location!!!  All this going on in the inner loop of the path finder!
<Edit: 20-May-09
As pointed out by Bork, this was not the reason the vector was causing a performance problem, rather it was removing elements from the vector from random positions, not just of the end.
>

This is big. Changing this to a STL list (implemented as a doubly linked list) is how I reduced the worst case processing time to a little over a quarter of what it was. Given the we have a maximum search node limit, I think we should actually just change this to a good old fashioned array, you can't beat a pointer for low overheads!

So that's the first Quick Fix.

Next Up: Annotated A*
I've already started implementing an Annotated A*.  Basically the first part of this article:
http://aigamedev.com/open/article/clearance-based-pathfinding/
The part dealing with 'true metrics'. (great article, I hope to implement the full HAA* in the not to distant future, should make Glest's Path Finder state of the art )
The only real issue implementing this, is we need to know when the map changes, specifically when a cell's “walkability” changes.

Here's the situation's I thought of so far, and where we can hook into them in the code:
//   Starting Buildings: in World::placeUnit() or Unit::Unit()
//   Built Buildings: in UnitUpdater::updateBuild () or Unit::Unit()
//   Destroyed Buildings: in Unit::kill() or World::doKill()
//   Building Grew Legs: in Unit::morph() ?
//   Resource/Tree Dissappeared: in SurfaceCell::deleteResource()

So, is that list complete? Does anything else modify cells, or make them walkable/not-walkable ?

[hailstone]

Good work. Morphing is definitely something that affects the walkability and also any other unit that moves (good example is when you have lots of workers on the same resource).

[silnarm]

Ok, quick update on the Annotated A*...

In a nutshell, it works...



There are still some minor issues to fix, and one major one.
I was held up by the inability to see what was going on, for which I required the clearance values to be drawn on the cells. Unfortunately, cells aren't rendered individually... 2 days and number of headaches later, I was able to render cell's individually, and I could start fixing things, but that was only yesterday....

should be a source patch ready by (or on) the weekend...

 

[wciow]

Wow excellent project, the path finding for workers/resources can get pretty bad at times. I'm gonna build some test maps to see how good this new pathfinding is 

should be a source patch ready by (or on) the weekend...

Will there be an option for an A* sandbox?

Any chance you could squeeze in an XML switch to make water walkable for some units?

[bork]

So, What is up with Glest's Path Finder?

[snip]

What I didn't consider at first, possibly because it was hidden away in a typdef, was what data structure are we using for the open and closed lists???
The answer was most surprising...
   typedef vector<Node*> Nodes;
An STL Vector!!!
You know, the ones that are essentially arrays, that can dynamically grow as needed, by allocating new memory and copying the old contents to the new (bigger) location!!!  All this going on in the inner loop of the path finder!

Do the vector growing really slows down algorithm??? Didn't you find out why it was resized so often? How did you tested performance? As I can see open and closed lists memory never reclaimed until destruction of PathFinder instance, so they should stop allocating/deallocating after few passes of the algorithm.

This is big. Changing this to a STL list (implemented as a doubly linked list) is how I reduced the worst case processing time to a little over a quarter of what it was. Given the we have a maximum search node limit, I think we should actually just change this to a good old fashioned array, you can't beat a pointer for low overheads!

So that's the first Quick Fix.

The thing which is really strange to me is why there is linear search inside minHeuristic at all, you could get some speedup by changing open list to priority_queue (which requires vector or dequeue as backing store anyway).

Also, if you want a good speed up you could consider using hierarchical routing algorithms. There will be difficulties with dynamical changing of nodes traversability, but if you could manage to overcome them it will make path finding really fast. Although, I have some doubts that path finding is a bottleneck for game performance.

[snip]

[silnarm]

Wow excellent project, the path finding for workers/resources can get pretty bad at times. I'm gonna build some test maps to see how good this new pathfinding is 

Will there be an option for an A* sandbox?

Any chance you could squeeze in an XML switch to make water walkable for some units?

There'll be no Sandbox I'm afraid, I can put some stats in the debug info, and allow you to change the algorithm used in the ini file...
A Sandbox mode for the game would be fantastic, would be very useful for testing, code and mods... and I'd love to make one, but to be realistic I've only just started looking at this beast, and it aint small! Just getting the pathfinder fixed up has led me to many places in the code I thought I wouldn't need to be tinkering, but I've still only scratched the surface... maybe one day... maybe

Water will be a 'Field' in the game soon enough, it will then get its own 'map' of clearance values, as will the combination land + water (for amphibious units). I've currently got the 'Metrics' (the clearance values for each field or combination) stuffed into 32 bits per cell, at 4 bits each (giving a maximum moveable unit size of 15) that's room for 8 fields (and any combos), which I imagine should be enough, but is easily increased anyway.
 

Do the vector growing really slows down algorithm??? Didn't you find out why it was resized so often?
How did you tested performance? As I can see open and closed lists memory never reclaimed until
destruction of PathFinder instance, so they should stop allocating/deallocating after few passes of the algorithm.

The precise re-allocation strategy would depend on the STL you're linking with, but I think you're right, it shouldn't shrink once it hits the node limit for the first time. It was probably the deletions actualy (?) vectors are only good (=fast) for deleting of the end, whereas we might need to delete any element from the open list each iteration.

I timed the calls to aStar(), and made an aStar2() that used a list, set the AI to use the vector based A*, while I got the list based one, timing stats were written to the log.

The thing which is really strange to me is why there is linear search inside minHeuristic at all, you
could get some speedup by changing open list to priority_queue (which requires vector or dequeue as backing store anyway).

Also, if you want a good speed up you could consider using hierarchical routing algorithms. There
will be difficulties with dynamical changing of nodes traversability, but if you could manage to
overcome them it will make path finding really fast. Although, I have some doubts that path finding is a bottleneck for game performance.

Unless you sort them into a tree as you insert then there's no option but a linear search.

I intend to implement hierarchical abstraction of the map at some point, that's stage two of the overhaul (and probably wont be a priority)... but clearance annotations will make it significantly faster than it is, and it's a severe problem at the moment for long paths. Though I tend to agree with you that, in general, it's not going to be the bottleneck.

[silnarm]

Also, if you want a good speed up you could consider using hierarchical routing algorithms. There
will be difficulties with dynamical changing of nodes traversability, but if you could manage to
overcome them it will make path finding really fast. Although, I have some doubts that path finding is a bottleneck for game performance.

Unless you sort them into a tree as you insert then there's no option but a linear search.

Hmmm... I'm going to claim sleep deprivation...
Obviously it needn't be a tree structure... furthermore.. why is it a linear search?!? we can keep the open list sorted, or at least the 'best bit' of it, the low end.
Well spotted! This is going to provide another nice boost!

[titi]

If you are working on the pathfinder, it would be nice if you would think about something like ships and water.
This would be a really nice thing to have in glest and I think it will effect the pathfinder too.( or am I wrong here? )

[silnarm]

If you are working on the pathfinder, it would be nice if you would think about something like ships and water.
This would be a really nice thing to have in glest and I think it will effect the pathfinder too.( or am I wrong here? )

Yep, water craft will not be far away

Probably got too technical ... at the expense of being understood!

In the reply to wciow I mentioned that what I've done so far supports 'metric maps' for 8 'fields' or combinations, Glest currently only has two fields, land and air.

I'm trying to keep the pathfinding as generic as possible, so a future version of Glest might (for example) have land, forest, sea, and air fields, and keep metric maps also for the combinations 'land + forest' & 'sea + land'.
So it could then support units that can
1. only move on (open) land (big stuff that you don't want to let through forests)
2. only move in forest, probably don't need this one
3. only move on the sea
4. only move in the air
5. move on (open) land or in forest (typical infantry)
or 6. move on the sea or (open) land (amphibious units)

That's just an example of course, the fields and combinations would be set up for the given techtrees needs.

For any given field, the path finder just needs to be told initially which cells are not traversable, and informed when any cells traversability changes... it will handle everything else.

Regarding water... the Path Finder will support it almost out of the box, there are already functions in the Map class to determine if a cell is underwater or not (actualy two, under water and 'deep' underwater)...  But there will be plenty of other issues to deal with, buildings 'hanging out' over the water (docks), loading/unloading land units, rendering issues/decisions and more... So don't expect it to happen quickly, but do expect it to happen

[hailstone]

Perhaps some time in the distant future different conditions might affect movement or other qualities (like defence). For example if you were walking knee deep in mud it's going to be slower than walking on hard ground. These things would need to be included in the pathfinding.

[silnarm]

Ok, didn't get a patch on the weekend obviously, and I still don't have one for you. But it is coming... less than 24 hours... sorry to 'tease', but I wanted to report some more results, and I'm to tired to get a patch ready tonight.

I can't break it anymore (can't crash the game), and I'm happy with the performance, so I'll package it up tomorrow night, and some other people can try to break it.

A quick note: it's Faster, not Smarter.

It's essentially the same algorithm as before, I just changed how the tests were performed, how the open & closed lists are implemented, and introduced some preprocessing to try and quickly determine if the target is unreachable. 

That is what was really killing the path finder as it was, A* failing to find a path is the worst case scenario (for processing time), and when many workers are going for the same resources, they often block access to the 'destination position' another worker wants to go back to. That spot might be three tiles away, but because it's "blocked in" the resulting A* search exhausts 400 nodes trying to get to it, fails and picks the 'least heuristic' to go to (often where he is already standing), next update? repeat. This is what was causing 'the' Glest slow down.

I've played a few games through with the new path finder now, and I can report no sudden frame rate drops, and I was getting chronic frame rate drops before.

Here's some numbers from the log of my most recent timing test, 1 human, 3 AIs, a tampered with MagiTech techtree (to accelerate things a bit... I've been doing a lot of testing...), all on teams of their own, Teams 0 and 2 were hooked up to the shiny new annotated A*, teams 1 & 3 used the old A*. The 'average' and 'worst' are measured in 'clock ticks'.

23: Launching game
81:
Vanilla A* : Total Calls: 143, Average: 314, Worst: 23935.
Annotated A* : Total Calls: 129, Average: 86, Worst: 970.
111:
Vanilla A* : Total Calls: 366, Average: 1580, Worst: 43239.
Annotated A* : Total Calls: 341, Average: 76, Worst: 1930.
<snip>
261:
Vanilla A* : Total Calls: 2133, Average: 2290, Worst: 43239.
Annotated A* : Total Calls: 2337, Average: 41, Worst: 5946.
<snip>
411:
Vanilla A* : Total Calls: 3656, Average: 2803, Worst: 52071.
Annotated A* : Total Calls: 4701, Average: 28, Worst: 6039.
<snip>
651:
Vanilla A* : Total Calls: 7324, Average: 5329, Worst: 53211.
Annotated A* : Total Calls: 10736, Average: 18, Worst: 9355.
<snip>
831:
Vanilla A* : Total Calls: 8969, Average: 4044, Worst: 53211.
Annotated A* : Total Calls: 14464, Average: 18, Worst: 9355.

As you might imagine from the average call time, the speed up is rather substantial.

More details, and the all important patch, to follow tomorrow...

Perhaps some time in the distant future different conditions might affect movement or other qualities (like defence). For example if you were walking

knee deep in mud it's going to be slower than walking on hard ground. These things would need to be included in the pathfinding.

Yeah, that would obviously need to be taken into account by the pathfinder, I was thinking of doing influence maps (for better ai players) some point down the line, these too will need to be taken into account by the pathfinder, we can use the same mechanism, I'll make it (down the line) so the  pathfinder can be handed one or more influence maps when asked to calculate a path.

Keeps it nice and 'generic'

[silnarm]

Well, it just gets better...

Turns out one of tricks I was employing, to see if the target position was accessible, was not checking
units, I'd commented out the lines when I copied them from the aStar routine... because it was initially
referencing a variable the new function didn't have, a subtle copy/paste error

Anyway, it perform those checks now.. and it's faster still...

http://www.mediafire.com/download.php?dj1gogmzmmm

Anyone who can compile, please try it out, if you can make it crash or you notice any bugs, please let me know...

Edit: Sorry, that's a patch on gae0.2.11, run it from the 'source' directory.

[assassin]

Um, whilst trying to download, mediafire tells me that the file is password protected.

[silnarm]

Um, whilst trying to download, mediafire tells me that the file is password protected.

Ok, not sure what that was about, but it should work now...

[assassin]

Thanks, now all I need is for the GAE website to work...

[orion]

http://glest.codemonger.org/home_page.php

[assassin]

I get this error:
# patch < gae-jpm.patch
(Stripping trailing CRs from patch.)
can't find file to patch at input line 4
Perhaps you should have used the -p or --strip option?
The text leading up to this was:
--------------------------
|diff -ru glest_game_nopatch/ai/path_finder.cpp glest_game/ai/path_finder.cpp
|--- glest_game_nopatch/ai/path_finder.cpp      2008-12-15 08:34:43.000000000 +1100
|+++ glest_game/ai/path_finder.cpp      2009-05-20 16:23:43.453125000 +1000
--------------------------
File to patch:

[silnarm]

I get this error:

sorry about that, didn't have my directories set up correctly... first time I've used diff to make a patch

http://www.mediafire.com/download.php?mmyz4yytxbd

this one should do the trick, run patch with -p1

[assassin]

Whilst compiling, I get a whole load of errors    :

..found 561 target(s)...     
...updating 65 target(s)...   
C++ ./build/i686-pc-linux-gnu/optimize/glest_game/ai/ai_rule.o
In file included from glest_game/world/unit_updater.h:16,     
                 from glest_game/world/world.h:29,             
                 from glest_game/ai/ai.h:18,                   
                 from glest_game/ai/ai_rule.cpp:17:           
glest_game/ai/path_finder.h:74: error: qualifiers can only be specified for objects and functions                                                               
glest_game/ai/path_finder.h:79: error: qualifiers can only be specified for objects and functions                                                               
glest_game/ai/path_finder.h:97: warning: type qualifiers ignored on function return type                                                                       
glest_game/ai/path_finder.h:109: error: qualifiers can only be specified for objects and functions                                                             

    g++ -c -o ./build/i686-pc-linux-gnu/optimize/glest_game/ai/ai_rule.o  -I/usr/include -DPACKAGE_NAME="gae" -DPACKAGE_TARNAME="gae" -DPACKAGE_VERSION="0.2.11" -DPACKAGE_STRING="gae 0.2.11" -DPACKAGE_BUGREPORT="http://bugs.codemonger.org" -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DUSE_POSIX_SOCKETS= -DX11_AVAILABLE=1 -DHAVE_GLOB_H=1 -DHAVE_SYS_IOCTL_H=1 -DHAVE_SYS_TIME_H=1 -DHAVE_BYTESWAP_H=1 -DUSE_SDL= -DHAVE_PTHREAD=1 -DHAVE_LIBZ=1 -I. -I/usr/include/SDL -D_GNU_SOURCE=1 -D_REENTRANT -pthread -pthread     -Iglest_game/../shared_lib/include -Iglest_game/../shared_lib/include/platform -Iglest_game/../shared_lib/include/platform/sdl -Iglest_game/../shared_lib/include/platform/posix -Iglest_game/../shared_lib/include/util -Iglest_game/../shared_lib/include/graphics -Iglest_game/../shared_lib/include/graphics/gl -Iglest_game/../shared_lib/include/sound -Iglest_game/../shared_lib/include/sound/openal -Iglest_game/../shared_lib/include/xml -Iglest_game/. -Iglest_game/ai -Iglest_game/facilities -Iglest_game/game -Iglest_game/global -Iglest_game/graphics -Iglest_game/gui -Iglest_game/main -Iglest_game/menu -Iglest_game/network -Iglest_game/sound -Iglest_game/type_instances -Iglest_game/types -Iglest_game/world   -Wall -W -Wno-unused -Wno-sign-compare -fno-strict-aliasing -O3 -g3 -DNDEBUG -ffast-math -ftree-vectorize -Winit-self -Wmissing-include-dirs -Wwrite-strings -Wextra -Winvalid-pch glest_game/ai/ai_rule.cpp

...failed C++ ./build/i686-pc-linux-gnu/optimize/glest_game/ai/ai_rule.o ...
...removing ./build/i686-pc-linux-gnu/optimize/glest_game/ai/ai_rule.o
C++ ./build/i686-pc-linux-gnu/optimize/glest_game/ai/path_finder.o
In file included from glest_game/ai/path_finder.cpp:14:
glest_game/ai/path_finder.h:32: error: use of enum ‘Field’ without previous declaration
glest_game/ai/path_finder.h:74: error: qualifiers can only be specified for objects and functions
glest_game/ai/path_finder.h:79: error: qualifiers can only be specified for objects and functions
glest_game/ai/path_finder.h:97: warning: type qualifiers ignored on function return type
glest_game/ai/path_finder.h:109: error: qualifiers can only be specified for objects and functions
glest_game/ai/path_finder.h:124: error: ‘Field’ has not been declared
^C...interrupted
...removing ./build/i686-pc-linux-gnu/optimize/glest_game/ai/path_finder.o

And that's just the start.. all the patched files don't compile and at the end of compiling the gae binary is nowhere to be seen. I think that the problem is with the .patch file, so perhaps you could just upload the modified files (path_finder.cpp, path_finder.h, unit_type.h, unit_updater.cpp, unit_updater.h, world.cpp).

I'm sure we can eventually get this working  

[silnarm]

Whilst compiling, I get a whole load of errors    :
...
And that's just the start.. all the patched files don't compile and at the end of compiling the gae binary is nowhere to be seen. I think that the problem is with the .patch file, so perhaps you could just upload the modified files (path_finder.cpp, path_finder.h, unit_type.h, unit_updater.cpp, unit_updater.h, world.cpp).

I'm sure we can eventually get this working  

Yikes...
The problem unfortunately is not the patch, it's my 'bad' C++, combined with the fact that I'm using windoze and the ms compiler is happy to let me do several things that are non-standard, gcc is being strict. Been programming in C# for a while, picked up some bad habits

glest_game/ai/path_finder.h:32: error: use of enum ‘Field’ without previous declaration
glest_game/ai/path_finder.h:124: error: ‘Field’ has not been declared

I was simply trying to forward declare this at line 32, so I could use it later (124). I'm very surprised this is not allowed... fixed by deleting offending declaration and including unit_stats_base.h

glest_game/ai/path_finder.h:74: error: qualifiers can only be specified for objects and functions
glest_game/ai/path_finder.h:79: error: qualifiers can only be specified for objects and functions
glest_game/ai/path_finder.h:97: warning: type qualifiers ignored on function return type
glest_game/ai/path_finder.h:109: error: qualifiers can only be specified for objects and functions

These are all (apparently) extraneous 'const' qualifiers. Fixed by removing 'const' from the declarations of AStarNode, PosTreeNode & NodePool (and the const in front of getMaxNodes() takes care of the warning).

Give it a try if you can be bothered... but there may be other problems. I'll have get a linux installation going, or maybe just use gcc under windoze, or try to cajole VC++ into behaving in a more standard fashion... either way I'll post a working patch soon... sorry for all the problems.

[assassin]

It's not just these errors, all the files that are patched give out that many errors. I'm not a very good c programmer so I won't do the modifications (I'll probably just break it even more). I look forward to the linux patch though.
Alternatively, is there anyway I can make gcc less strict?

[wciow]

Anybody got this working yet?

If so could someone please post a patched GAE executable for windows.

I would do it myself but i don't have the tools, time or coding knowledge   :'(

[silnarm]

I've played a few games through with the new path finder now, and I can report no sudden frame rate drops, and I was getting chronic frame rate drops before.

I should have known better than to make such bold claims on the basis of a few test games...
It does seem to be better (drops go away quicker), but I think I might be imagining things

The slow down was not related to the path finder, of course the old one was misbehaving and frequently 'blowing out', doing exhaustive and fruitless searches where no path was possible, for example.  So this was all worth while... and when I throw some hierarchical abstractions over the top, we'll be able to play on BIG maps.

wciow and others, I've got a linux box up and running, so hopefully on the weekend I'll get some time to have a play on it, and make my MS C++ into standard C++. I didn't want to release binaries myself, being new here and something of an unknown.. but it appears, for windows at least, I may have to. Give me a day or two to get things organised.

<technical>
Regarding the slow down, I've done some more testing and I have it nailed down now, OpenGL is blocking on SwapBuffers() (which I'm pretty sure it shouldn't be). I'll have to do some reading (well, probably a lot) and play around a bit more, the linux box has a NVidia card, so it'll be interesting to see if it behaves the same (this machine has ATI), I'll test it out on my gfs laptop too, which is using some Intel chip.
</technical>

[silnarm]

Regarding the slow down, I've done some more testing and I have it nailed down now, OpenGL is blocking on SwapBuffers()

This latest misinformation brought to you by my passing 64 bit integers to sprintf().  The numbers I was looking at for swapBuffers() were infact the numbers for render3d().  But render2d() also blows up at the same time, everything will be running smoothly, then the renderer will choke, sort itself out, repeat...
bah... I'm giving up on this for now, I'll never get anything done if I keep chasing this thing.

Better Paths, Dirt Cheap!

So, back to the pathfinder, I'm happy that it goes suitably fast now, so I thought I'd look at trying to improve the path quality a bit.  Glest's A* algorithm (which isn't very A* like) returns bad paths primarily because it tries to shoot straight at the target, and if something gets in the way, it just edges it's way around, whereas proper A* will be consider many many more positions, and can hence realise there's a better way around the obstacle. Full blown A* is out of the question though, for too 'expensive'.

I've been reading 'Near Optimal Hierarchical Path-Finding' [Adi Botea et al] in preparation for phase 2 of the overhaul, while that's not happening just yet, I did notice that they (optionally) 'smooth' their paths, to improve quality, by replacing sub-optimal path pieces with straight lines. Sounded good to me, and it would fix up most of our dodgy paths.  Unfortunately they only really dedicated a paragraph to explaining this in the paper, so I downloaded the source and had peek... Yuck. I thought they might have come up with cool and efficient means to do this, but I'm now guessing rather it was an 'afterthought' and tacked on.

Then I thought, this thing is pretty fast... why not run it twice for each search ?

Shown below is on such search, the yellow cells are those on the path from the start to the destination, the red ones are the path from the destination to the start, yellow and red ones are on both paths.


So, run it once each way, where they diverge start counting how long each segment is, and pick the better one to 'stitch in' to our final 'solution' path, voila, quality paths...


I haven't timed it much yet, but calculating a path from one corner of "Conflict" (64x64 map, [that's 128x128 cells though]) to the other took just over 2ms on my 'first go', the return journey was almost bang on 3ms [on a 2GHz AMD Turion64x2, release build]. So it's still quick enough for our purposes I think.

I'm calling Phase One complete. (barring bugfixes, of course)...
It'll be on the SVN tomorrow probably, just need to make sure it all compiles under linux.