TGB 1.7.3 Beta aStar discussion

#21 Ok, that makes more sense--in effect, you're talking about designated waypoints, which would probably override the underlying grid weights? That last so that we don't make it an "either but not both" situation?

#22 I was really thinking of a completely different and probably separate implementation of a path-grid. While a regular grid, perhaps based on a tilelayer, would be ideal for a Tower Defense game ... a sparse-waypoint based nav-grid could be better for other games. It would also perform a lot better in large-levels because there are fewer nodes.

I really don't know what "overriding" the tile weight below a waypoint would accomplish? I do not think you would want waypoints actually ontop of your nav-tiles. You could either use one or the other. If you did want to use both ... you might design waypoints that have the ability to "link-up" with the tilelayer.

Eg. part of your level is navigated by a tilelayer ( which covers that section ), and part is navigated by a net of waypoints. Then some special waypoints have links to a particular tile. So you can travel from waypoint to waypoint then onto the tilelayer through the connection waypoint-tile link.

#23 Well you could get good performance with a full grid A* as well if it gets updated to HPA* (hierarchy A*) which basically does nothing else than "mipmapping" the A* granularity from a very top level where it calculates only the path portals it has to travel to, where the actual paths are calculated in the underlying granularity levels.
This kind of A* needs some preprocessing in the editor for the portals etc to have different hierarchical levels of the grid (with 3 levels for example you have the full detail which works on the tilemap cells, then one above that calculates the portals and paths between grid cells (10x10 tilemap cells for example) and then on the top level you have the same again with super grid cells of AxA grid cells and portals)

They are normally "pretty easy to implement" if you have a working A*, the only "non trivial" thing are portals.

That way you might get the best performance for both while still only having to maintain a single system for the purpose.
The only ones having problem on that case are those not using tilemaps at all but those will always have problems as the AI needs to be world aware to be able to avoid free placed objects. In that case potential field based pathfinding or path nets are much better.
Theoretically both sides could be pleased: if the editor would generate a node net with all tilelayer cells with a weight < 10 and the possibility to add and connect waypoints would be added, similar capability to "tilemap grid based" path finding would exist while still giving the flexibility of pure path nets for those without a grid or those that do not want to use the grid for movement calculations for example.

A link for those interested in a more descriptive full explanation of the idea of hierarchical A*: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#S4


I really welcome the addition of an integrated A* solution as it will allow development of much better (and less CPU consuming) games that use AI agents in the future than currently, at least for those without the sources.

#24 Hi all,

First, I'd like to say thank you for the aStar implementation, and the demo. It was quick and easy to implement.

However, I have a question regarding cleaning up old paths.

I keep spawning enemy objects which are in the aStarActor super class. They make their way through the maze just fine. When they reach their destination, a counter is increased, and the enemy object is deleted.

What happens to the aStar path, if I only delete the enemy object? I believe the path is an object itself, and only the reference (stored within my enemy object) gets deleted.

After a handful of enemies make their way through the maze, my game freezez up and errors out. I'm afraid that the rogue paths are using up extra memory space, and aren't being cleaned up.

What, if any, clean up is required, when I delete my actor?

Thank you,
Johnny

#25 It sounds as if your hypothesis is correct...if you are starting to bog down with just a "handful" of enemy spawns, it actually seems as if you are creating a new path every time you update your enemy objects.

The aStar demo files have a call back that is intended to be triggered when you delete your enemies:

function aStarActor::die(%this)
{
   if (isObject(%this.currentPath) )
   {
     //echo("aStarActor::die--removing path (" @ %this.currentpath @ ")");
     %this.pathGrid.deletePathID(%this.currentPath);
     %this.pathGrid = 0;
   }
}

Normally what you should do if you are using the aStarActor class is to have a trigger on your enemy's die function:

function Enemy::die(%this, %reason)
{
   // clean up our object, including all of our aStar housekeeping
   aStarActor::die(%this);
   
   // in our tutorial, we can only have one reason for dying ("escaped"), so we don't use
   // the %reason parameter. In other games, you will probably have different reasons for calling .die()
   // on your aStarActors, such as "destroyed", "escaped", "timedOut", or whatever your game requires.
   
   activeActorsSet.remove(%this);
   %this.safeDelete();
}

I would also suggest you study the code in depth within the demo, specifically how the aStarActor class handles the difference between a "one time path test", and a path that is intended to be reused extremely often.

A good point to start would be the startPath method:

function Enemy::startPath(%this, %start, %dest)
{
   // find our path
   %this.pathGrid = $pathGrid;
   %newPath = %this.findDestinationPath(%dest);
   if (isObject(%newPath)  )
   {
     %this.currentPath = %newPath;
     // for games that require the ability to test a world change before making it permanent,
     // we want a testing path that isn't created/deleted often, which will speed up our validation
     // of a player's "move" that changes our world. This is unused in the demo, but we leave it in
     // for other game types:
     
     %testingPath = %this.findDestinationPath(%dest);
     %this.testingPath = %testingPath;
     %this.followAStarPath(%newPath);
     activeActorsSet.add(%this);
   }
   else
   {
      %this.isFrustrated("noPath");
   }
}

#26 Hey guys,

I'm trying to implement aStar API into my turn-based strategy game.

The main scene of the game is a battlefield full of square tiles.(which is perfect to hook up with t2dTileLayer) Different tile will cost different "movePower" of the unit. For example if the unit travels on only on grass he can move 5 tiles away in one round, but only 3 tiles on forest. Please consider Heroes of Might and Magic for reference.

First of all, I set up customData for each tile, say 1 for grass, 2 for forest. When player select a unit, I want to use aStar API to test certain amount of tiles around the unit to see if after all the "movePower" cost how far can the unit travel.


So I pick a tile as destination, and run findDestinationPath(%dest)

%testPath =%unit.findDestinationPath(%dest);

Now I have a path, but how can I check through each tile on the path and calculate the "movePower" cost? The closest approach I can see is to access each node on the path using

%nodeWorldCoords = %this.currentPath.getNodeWorldCoords(%nodeIndex);

Unfortunately aStar API will only add a node to the path when the unit have to take a turn to follow the path, which means if the unit travels 5 tiles in a line, the path will have only 2 nodes, the start and destination.

So I need a way to access each tile on the path, not only nodes. Is it possible for the current aStar API? Also unfortunately I don't have access to c++ code of the engine. Please someone tell me there's another way around before I'm forced to upgrade the engine..

Any tips and inputs is appreciated!