B4A Library [Lib] Steering Behaviors

This library will bring life to the animated characters of your game by giving them autonomy. It is based on the Craig Reynold's article: Steering Behaviors For Autonomous Characters.

Let's imagine a game where a cat pursues a mouse. You have to write the code to move the mouse, to move the cat and to take the right decisions for both: the cat wants to catch the mouse, the mouse wants to evade the cat. This library will do this very easily. You create two vehicles: a cat and a mouse, with an initial location, a maximum speed, a mass, etc. Then you add their behaviors (with the Steer function) in the main loop: Pursue for the cat, Evade for the mouse. You apply these behaviors with Cat.Move and Mouse.Move, and that's it. You're ready to watch them running around.

You have many behaviors available: Align, Arrive, AvoidObstacles, AvoidVehicles, Cohere, Evade, Flee, FollowPath, Pursue, Seek, Separate, View, and Wander. By combining them, you can create new behaviors like Flock, FollowLeader, StayOnPath...

Starting from version 2, the library is released as a donationware. That means: if you want to use it in your application, please donate something by using the link in my signature. I'll send you the file as soon as I receive your donation.

You can donate what you want, from one dollar to one million dollars (for such an amount, you'll be my friend forever ).
I don't do that to earn a lot of money, just to be rewarded for my work (and I probably won't earn a lot of money this way ;-)).

Thanks in advance for your support.

Version 1.1 Free
11 behaviors: Align, Arrive, AvoidObstacles, Cohere, Evade, Flee, FollowPath, Pursue, Seek, Separate, and Wander.
11 examples.

Version 2.3 Donationware
13 behaviors: Align, Arrive, AvoidObstacles, AvoidVehicles, Cohere, Evade, Flee, FollowPath, Pursue, Seek, Separate, View, and Wander.
Align, Cohere and Separate have an additional parameter: VisionAngle.
New classes: SB_Grid, SB_Node and SB_Pathfinder, with new functions for pathfinding (based on a very fast variant of the A* algorithm)
14 examples.

I provide help only to my donators.

The Accelerated Surface library is required to run the examples.

 

[Informatix]

Thank you, i learned again something new from you.

I like the steering behavior lib. It is really how you allready said "bringing life to your characters"

We have to thank Sterlingy. He pointed me to the original paper of Craig Reynolds and provided the financial support to create this library. I never tried to do IA stuff before that so I learned something important too.

 

[ilan]

Thank you @sterlingy

Btw i am interested in ver2, when i will start the relevant game i will send you a donation...

 

[Informatix]

New version for donors:

My new variant of the A* algorithm is 2x faster. I never saw anything faster among Java codes available on Internet. Only a conversion to C could perform better but it's fast enough in Java for almost all needs.
I also added a few things to customize even more the algorithm.

v2.3 (for donors only):
- I greatly improved the performance of the A* algorithm in SB_PathFinder;
- I added HEURISTIC_CHEBYSHEV to SB_PathFinder;
- I added HEURISTIC_NONE to SB_PathFinder (turns the A* algorithm into a Dijkstra algorithm);
- I added a DiagonalMove parameter to SB_PathFinder.CreateGrid;
- I added TotalCost to SB_PathFinder to get the total cost of a path;
- I replaced COST_GRID by COST_GRID_DIAG_DOUBLE, COST_GRID_DIAG_SAME and COST_GRID_DIAG_SQRT in SB_PathFinder.

 

[ilan]

hi

does this lib also contains the "flow field following" method of steering behavior? http://www.red3d.com/cwr/steer/FlowFollow.html

thank you

 

[Informatix]

hi

does this lib also contains the "flow field following" method of steering behavior? http://www.red3d.com/cwr/steer/FlowFollow.html

thank you

The flow field array is an array of steering force vectors. You just have to apply the given force to the vehicle velocity. There's no need to add this to the library.

 

[peacemaker]

HI, Informatix,
Is it possible to use your lib for offline routing (way directions) over an offline map, say Google's ?

 

[Informatix]

HI, Informatix,
Is it possible to use your lib for offline routing (way directions) over an offline map, say Google's ?

What do you mean exactly? Is it able to compute the fastest path between two points on a map? Yes (for the paid version). It can use the A* and Dijkstra algorithms (A* is faster but does not give always the optimal solution). But it cannot work directly from a Google map. You have to encode the map to a graph with a node for each crossing.

 

[peacemaker]

Thanks, clear. So, main problem is with the array of roads crossings with coordinates... that should be terabytes on Google Map servers ...

 

[Informatix]

Thanks, clear. So, main problem is with the array of roads crossings with coordinates... that should be terabytes on Google Map servers ...

There's no path computation in the Map API?

 

[peacemaker]

There's no path computation in the Map API?

Only online requests to the server. But there are customers who want offline map routing. So, replay for them now is "impossible".
Seems, some other map services have this feature, but... not for B4X.

 

[Erel]

Google Maps SDK doesn't support it.

 

[peacemaker]

It would be very nice to have the simplest code sample for a single FindShortestPath usage.
Just mathematic path finding, without sprites on a screen, list of the points IDs from the start to finish.
The samples now are very nice, but ... very complicated to start understanding... Minimal code comments

How Nodes are used ? No sample. I need to setup the allowed point for the FindShortestPath.

 

[Informatix]

It would be very nice to have the simplest code sample for a single FindShortestPath usage.
Just mathematic path finding, without sprites on a screen, list of the points IDs from the start to finish.
The samples now are very nice, but ... very complicated to start understanding... Minimal code comments

How Nodes are used ? No sample. I need to setup the allowed point for the FindShortestPath.

The pathfinding algorithm is for vehicles moving on a map. Without a map or without navigation costs, that's pointless.
The minimal code is:

Dim PF As SB_Pathfinder
Dim Grid As SB_Grid = PF.CreateGrid(LeftTop, RightBottom, CellSize, Null, True)
Dim lstWaypoints As List = PF.FindShortestPath(Grid, StartPosition, EndPosition, PF.HEURISTIC_DIAGONAL, PF.COST_GRID_DIAG_SQRT, "")

The map is divided into square cells to ease the pathfinding (trying to find a path at the pixel level is a complete waste of resources, so the algorithm operates on a bigger matrix).
Let's take an example with four cities:

The navigation costs should be set to 1 for cells where there's a road and 10 where there's no road (or lower if you allow to go off road).
The shortest paths from the city B to the other cities are:

That works fine in a game, but in the real world you cannot create a grid for the entire world, even with big cells. So you do not base the computation of costs on the distance between the cells. You have to create your grid differently and use the Cost event to provide costs:

Sub YourPrefix_Cost(C As Int, R As Int, NeighborC As Int, NeighborR As Int, Diagonal As Boolean, GridCost As Float) As Float

In the map above, each city is connected to another city, like in the real world, but there's no distance between them. Practically, your grid should contain all crossings, not only cities, because there are more than 8 possible destinations from a medium-sized city.
When the Cost event is raised by FindShortestPath, you have to return the cost for travelling from C,R to NeighborC,NeighborR. For example, between A and B, you would return 5.
Is it clear now?

 

[Informatix]

...and once you found the shortest path with the above method, you can use the first grid, which contains the road between A and B, to get a list of waypoints. Many games and GPS softwares use a multi-grid system, with different levels of details, to find a path and get the waypoints.

 

[peacemaker]

But how to setup these A, B, C, D, E, F, G points in your objects?
I think that all cells in the matrix should be with cost=1 (allowed). Start-A to Finish-G via any of BCDEF.
Task is to get shortest way via the fixed coordinates of the crossroads (not all !) from the start to the finish, thinking that any cell is available to pass. No obstacles.

 

[Informatix]

But how to setup these A, B, C, D, E, F, G points in your objects?
I think that all cells in the matrix should be with cost=1 (allowed). Start-A to Finish-G via any of BCDEEF

Each node (= cell) has three properties: location (column, row), cost and tag. With the Tag, you can give an explicit name to the cell but it's only for you; it's not used. The cost allows to simulate varying terrain difficulties (obstacles, rough terrain, elevation, etc.) and, as said above, is only useful if you rely on the distance on the map between cells. If you prefer to use custom costs with the Cost event, this cost property is useless. You provide the cost to navigate from a cell to another so this cost simulates also what you want (e.g. distance in kilometers, number of minutes, etc.). The third property, the location, is very important when you want to determine waypoints on a map. If you use the method explained above to find the shortest path between numerous cities, the location is just useful to set the connections between cells (can I go to this node from this node?). The distance between is useless.
There's no A, B, C or D to put somewhere. It's a visual representation for the explanation.
You may have for example a database with 4 fields: "place name", "locationCol", "locationRow", and "connectionID" which points to another table where you record a list of "connected to" and "connection cost". With that, you know where is what, what is connected to what, and the cost to travel. The navigation grid will be used only to find the path, not to store data.

 

[peacemaker]

How\where SB_Node objects can be used ?

Is it correct that for my task i need to make
1) generate the grid where all cells are of a middle cost, say =5 (what are the costs after initial PF.CreateGrid?)
2) for Start, Fihish and middle points - set the cost = 1
And the way will be calculated via these points ?
Is the obstacle rectangle around the world required for sure for my one-way task ?

UPD: routing was without errors at last, but .... not via the middle points :-(
But costs are not set for these points...

 

[peacemaker]

It's very pity that SB_Vector2D has no "Tag" property, to identify the source points (before grid creation and after) much easily.
Possible to add ? It's no influence to the existing source codes.

 

[Informatix]

It's very pity that SB_Vector2D has no "Tag" property, to identify the source points (before grid creation and after) much easily.
Possible to add ? It's no influence to the existing source codes.

???
When you create a Vector2D, you create it with a variable name, so it has a name to identify it, and this Vector2d is not passed/returned by the FindShortestPath function so what's the usefulness of Tag in this case?
The waypoints list contains SB_Vector2D objects but they are created by the FindShortestPath function when a path is found so their Tag would be null in any case.

 

[peacemaker]

Informatix,

When i use 2 kinds of vectors, after finding the path - i must know which vectors have been used, so vectors kinds are different (for me).
PathFinder is made as a class, so input points are passed to the class.
2 point kinds: special and others. And if used special - i must identify them.