TGB 1.7.3 Beta aStar discussion

#1 Was there any particular reason that aStar is implemented on an object through the class/superclass namespace and not through a behavior?

#2 Well, it is based on a resource that was written pre-behaviors. Also some of the data used for AStar can be shared between multiple Agents, giving each Agent its own copy is wasteful. But I'm sure some compromise between behaviors and shared data is possible.

#3 This is definitely a topic we want to discuss with everyone :)

I'm an old school developer, so when I do prototypes (which the aStar implementation originally started off as), I tend to use the normal class based system. Consideration was given to behaviors for the aStar API before we went to beta, but we felt it would be better to get feedback on how to design the system within the behavior architecture from you guys, the users.

It might be an awesome time to break out what the key behaviors within the tutorial as you guys explore, and I'd like to get fresh feedback before we start our side of the interactive conversation, so if anyone is up for giving a first run through of behavior ideas with a one sentence or so description of each, that would be awesome!

#4 We're still looking for feedback on the aStar implementation, as well as the aStar tutorial, so please join us in discussing how we can make it better :)

#5 I was going to post this a couple hours ago but my internet went down. :P

Okay, I've been working on a demo level with A-Star behaviors. It's still a work-in-progress but I've jotted down a few ideas as a rough framework based on the existing A-Star API with all the butterfly demo code removed.

Things needed in a scene for A-Star: (min. 1) Scene Object, Tile Layer

Basic tasks that need to be encapsulated in behaviors/script:
1. Something that kicks off the path finding/movement process - i.e. player input, a schedule, an event.
2. Find/Calculate a path - requires a starting point (usually the current position of scene object) and a destination or end point. Those requirements should come from task 1.
3a. If a path is found: Move along that path. Allow hooks for callbacks when specific nodes along the path or the destination is reached.
3b. If a path is not found: allow the object to do something (or nothing)

Potential Behavior Types:
Path Layer Behavior- creates a pathGrid2D object, contains pathGrid2D specific functions. Attached to tile layer.
Path Finder Behavior - contains all the functions for calculating/finding a path. Attached to a scene object.
Path Follower Behavior - contains all the functions for moving along a path. Attached to a scene object.
No Path Behavior - attach to a scene object to allow the object to do something when it is "frustrated". (optional)
Endpoint Behavior - attach to a scene object to allow the object to do something when the destination point or object is reached. (optional)
Midpoint Behavior - attach to a scene object to allow that object to do something when a specific node or nodes are reached along the path. (optional)

Other Behavior Types:
Destination Behavior - attach to a scene object to define it as a destination. (as seen in the aStarDemo)
Mouse Event Behavior - attach to the tile layer to enable mouse events and point and click movement of a player controlled scene object. (point clicked is defined as the destination of a path)

That's what I have for now. The proposed path finder/follower behaviors could be combined into 1, which would then basically be exactly like the aStarActor script though.

#6 On a separate tangent to the behavior discussion aspect of A-Star, there are also a few things for the Editor that would come in handy.

1. Having debug rendering options available via script and the editor which would show a visualization of the path an object is planning or currently taking.

2. An upgrade to the tile editor to allow a better visual display of custom data, at least in how it applies to A-Star. It would be nice to see the weighted values of each individual tile in the layer instead of just a small C icon on each tile.

#7 I didn't see this really mentioned in the docs so far, but I had a bit of trouble at first with how to weight tiles. For my demo level, I thought I could do something simple like walk/don't walk with adding the value 0 to a tile for walk and 1 to a tile for don't walk.


In this picture if the grass has 0 in it's custom data and the trees have 1, the butterfly will walk through the trees to where the black X is. This isn't what I wanted though, the intent was to have the trees act like a wall that can't be walked through. Upping the custom data field to 5 on all the trees told the butterfly to follow the yellow path, which met my expectations.

It would be good to have something in the docs to explain the weight concept and how it needs to be applied if you have a large body of water (or trees) that you do not want an object to walk through.

#8

Quote:
1. Having debug rendering options available via script and the editor which would show a visualization of the path an object is planning or currently taking.

2. An upgrade to the tile editor to allow a better visual display of custom data, at least in how it applies to A-Star. It would be nice to see the weighted values of each individual tile in the layer instead of just a small C icon on each tile.

Both excellent ideas!

1) There is some debug rendering code at the lowest level, but it's a big buggy and has some issues:

----unusual use of some of the stock Torque templates that throw asserts in debug mode (just needs some cleanup in design)
----an issue with cleaning up multiple paths that leave render artifacts in the display--enough to make it usable, but not particularly useful.

2) This one irked me a bit as well when I was working on the prototypes. I considered working on some sort of custom rendering mode for tilemaps that displayed the relative weights assigned to the matched path grid, either via the customData, or the path grid itself, but it wound up well out of scope for the initial implementation.

#9

Quote:
I didn't see this really mentioned in the docs so far, but I had a bit of trouble at first with how to weight tiles. For my demo level, I thought I could do something simple like walk/don't walk with adding the value 0 to a tile for walk and 1 to a tile for don't walk.

Definitely an oversight, and will be corrected before final.

For reference, the algorithm allows weights from 0 to 10, with 0 being no cost to travel (empty), and 10 being unpassable.

In your demo level, you're seeing that the zero weight grids are cheaper to use, but if you extended out additional "wings" to the left/right, you would eventually see the butterfly going ahead through the center area with a customData of 1.

#10 Having written several A* systems, the ability to affect the weight engine is vital to tune the A* to the desired effects. Especially in something like TGB, that needs to remain generic for many types of games. For performance, the engine should remain in C++, but still have the ability to pick a particular weight calculation system perhaps. Like being able to swap out a diagonal shortcut costing for a manhatten method costing, or perhaps a behavior that finalizes the cost calculation.

For reference what weighting system is being used? I really couldn't determine a clear determination by reading the code.

I'm not sure about the limiting scoring values of tiles either, 0-10 seems pretty inflexible for large complex scenes.

just my $0.02

--Rod

#11 I agree, being able to have more control over the underlying implementation is definitely in the plan for future releases.

You mentioned a couple of different parameters for control:

--weight calculation algorithm
----diagonal shortcut costing
----manhattan method

Any other options that would make the implementation robust enough for a variety of uses?

I can see your point as well regarding the limitations of 0-10 in a more complex scene as the only weights, and will take a look at a more detailed system for the future. Would love to hear any ideas!

#12 Here is an interesting idea that is implemented in the immersiveAI A*...

When getting the total cost of a node in the A* algorithm, in addition to whatever static weight/cost a node is assigned, a custom function is called in which you can perform any custom calculations which should affect the way nodes are weighted for this particular path. Some of this could be way too computationally expensive in script ( if you have a large area to A* and it calls this for every tile ) so it would be nice to support handling this in either C++ or script.

For example:

"Make a path from A to B and prefer nodes that are next to lava."

function calcTileCostModifier( %layer, %tileCoord )
{

   if ( $pathModifier $= "PreferLava" )
  {
   %tilex = getword(%tilecoord,0);
   %tiley = getword(%tilecoord,1);

   %cost = 10;
   if ( %layer.getTileImage(%tilex - 1, %tiley ) == LavaImage )
      %cost--;
   if ( %layer.getTileImage(%tilex + 1, %tiley ) == LavaImage )
      %cost--;
   if ( %layer.getTileImage(%tilex, %tiley - 1 ) == LavaImage )
      %cost--;
   if ( %layer.getTileImage(%tilex, %tiley + 1) == LavaImage )
      %cost--;
   if ( %layer.getTileImage(%tilex - 1, %tiley -1 ) == LavaImage )
      %cost--;
   if ( %layer.getTileImage(%tilex + 1, %tiley + 1) == LavaImage )
      %cost--;
   }

   return %cost;
}

#13 I do really like the idea, but your concern is a strong one (a callback to script for every tile is most probably going to be prohibitively expensive), so here's an alternate strategy:

--make a different tilemap for each "type" of behavior (such as "prefer paths near lava"), and assign different pathGrids to different aStarActors based on these behaviors.

Pros:

--still super cheap (relatively)
--can have as many pre-calculated weight maps as you like (memory footprint permitting)
--can have multiple objects with same behaviors all use their own pathGrid.
--can be done in current implementation (1.7.3)

Cons:

--can become complicated quickly, especially with 10+ weight grids (from a design perspective), each having to be related. Possible solution: have a pre-calculate step in your production process that takes an existing weight map and modifies it based on parameters
--reduced flexibility at run time
--increased memory footprint
--dynamic changes to the weight map would impose high performance costs since the change has to be propagated through multiple pathGrids (losing the pre-calculation step and it's performance wins)
--??

#14 A couple of things that pop out are the myriad of options one could have for steering control.

It would be pretty simple then to add behaviors based on the pathing to add some nice value behaviors to the core.

Avoid, Pursuit (chase), Evade, Contain , Flock , etc.. could all be stock behaviors, that could easily be assigned to objects or groups of objects. Which would allow people that do not have the c++ capability to derive their own some nice controls.

Avoid : Assign to an Object, and set a value of its avoid object .. ie .. turn and run.
Pursuit: Assign to an Object, and set a value of its target object .. ie .. chase.
Evade: Assign to an Object, and set a value of its evade object. More complex than avoid , but object wont leave an area.
Contain: Assign to an Object, and set coordinates like World Limits.. object will meander around the area.

Flock: Assign to an Object, set its Leader Object or Sim*..
Follow: Assign to an Object, set its Leader Object. (fun pet system)....
Join: Assign to an Object, set its Leader Object. Different from flock, because it needs to find a safe resting place.
For RTS etc. the group based movements would be really nice.

Having the ability like I mentioned previously to change out costing algorithm is really because the high variant of movement choices depending on screen complexity.

BTW. I really like where this is headed already. I think exposing just the right amount of control will be key to its flexibility and performance, obviously you can't be everything to everyone. But being able to pick a few things that aren't that hard to swap out , like the calculation algorithm will make this a really nice implementation.

#15 A* pathfinding often only deals with finding a path from two known locations around static obstacles. And I don't know if GG has any plans on implementing dynamic-obstacle avoidance or steering behaviors to go along with this A* pathfinding... Although most games that need one need both.

For the most part the two are separate systems. But sometimes the pathfinding system has navigation information which would improve the appearance of the steering behaviors, if it could only access it. ( eg. flee an enemy while taking into account the node costs - so you don't steering straight into a lake - for instance ).

I've tried several ways to accomplish this...

Something similar to "Inverse Steering" as described in an AI G.P.W. article. Take the steering force output by whatever steering behaviors are active and then adjust it ( by as little as possible ) to make it point at a nearby navigation node that is travelable.

Generate a short path all at once by taking the steering force multiplied by a path length - find the closest node to that position and then generate a path to it.

Convert the untravelable navigation nodes into "walls" and "obstacles" ( in the steering behavior sense ), and then use raw steering behaviors ( this would not consider the range of weights a node could have - just travelable or untravelable ).


On the other hand a simplistic implementation of the steering behaviors you mentioned using only the A* pathfinding could be done fairly quickly -- i just don't think it would look very good.

A resource providing the things described above would without-doubt be useful to many, but I don't know if that is really being considered -- since steering is usually a separate topic than A* and pathfinding.

Stephen?

#16 James is right--steering is normally considered apart from aStar, but I agree with both of you that a combined/designed interface between the two would be awesome to have :)

Two things that concern me off the top of my head with tying them together, at least in an early stage:

--currently, aStarActors are designed to not take collision/physics into account, other than the moveTo(%node) concept. An integrated steering system would probably need to take collision into account as well as grid paths.

--we would probably want to avoid directly affecting the pathGrid weights itself while calculating steering goals/inputs. Having to constantly re-calculate paths could get expensive, so we would want to change the way aStarActors react to path information, instead of how they calculate path information.

#17 Yeah I wasn't implying to bind these two concepts.. I was just thinking out loud how having the one properly done would allow the second with relative ease to be accomplished using some commonality.

But back on target with A* discussion, I didn't mean to "Steer" it off path :-)

#18 Two feature ideas:

Hand placed nodes and connections that are not part of a tilelayer. Imagine a game in which movement is not tilebased -- walls and obstacles are not all exactly the size of a tile or at the position of a tile. It might be preferable to hand place navigation nodes around your level and connect them also by hand as you see appropriate. Then A* could operate as normal, perhaps with a distance heuristic, to generate paths between these nodes.

Generation of a navigation node-grid based on empirical testing ( eg. collision tests ). If we stayed with the concept of a tilelayer for storing the navigation info -- the "generate nodes" code might look something like...
For each tile do a pickrect for its size/position looking for sceneobjects in the designated "obstacle's" graphGroup. If one was found - set that tile/node to untravelable.

#19

Quote:
Hand placed nodes and connections that are not part of a tilelayer.

aStar by definition has the concept of a "grid", in that the weights have to have a location in space. You can achieve the concept you are looking at by a combination of two techniques:

--decrease the world size of a specific tile location by increasing the number of tiles in the tile layer. WARNING: The performance cost of calculating paths goes up very quickly with the number of nodes in the grid. Empirical tests on my laptop (Dell Inspiron 9300, almost 3 years old) shows that much more than a 40 x 30 grid starts to noticeably impact performance--enough to be human noticeable.

--use the updateWeight and notifyActors API methods to re-calculate paths during run time. As has been noted in the comments on the .plan, the last image in the game looks suspiciously like a "make your own maze" style Tower Defense game--stay tuned after the beta is complete for more information!

Quote:
Generation of a navigation node-grid based on empirical testing ( eg. collision tests ). If we stayed with the concept of a tilelayer for storing the navigation info -- the "generate nodes" code might look something like...
For each tile do a pickrect for its size/position looking for sceneobjects in the designated "obstacle's" graphGroup. If one was found - set that tile/node to untravelable.

You can already do that as well--just detect collisions as you state, then update the weight grid with the method above.

#20 Here is what I meant by "Hand placed nodes and connections that are not part of a tilelayer".
Nodes are red, links are green, the cost of a path ( or weight ) is black text.


If the potential paths for your ai units are few - or do not fit well into the tilelayer mold - you might want to design something like that, in which each node and link are hand placed in your level.

aStar does not have to operate on a regularly spaced grid. This illustration meets all the requirements for pathfinding. Eg. find the shortest path between the marked startNode and endNode.