B4A Library A* (Astar) Library (B4J also)

derez

Expert
Licensed User
This library can be used to find the shortest route between two point in a net of nodes (like a matrix in a game or net of roads).
The library needs a public sub in the calling module named
[Eventname]_Neighbors(x As Double, y As Double) As List
This sub should provide a list of all neighbor nodes.
Another sub that may (or may not) be used is the sub that calculates the distance between two points.
If it doesn't exist, the library uses a simple distance: Sqrt((x1-x2)^2 + (y1-y2)^2).
If you want To use a more sophisticated cost calculation, for example the time of passing the leg (distance/speed) then you should include another Sub In the calling module:
Public Sub [Eventname]_Distance(dbl() As Double) As Double
The library will use that sub if it exists.

Please let me know if there are any malfunctions or anomalies in the operation of the library (it is based on published pseudo_code but includes some added improvements by me.

Edit: Ver 1.1 now works on other types of nets, see post #4.
Edit: Ver.1.1 library doesn't work on B4J, so I added a jAstar library.
Edit: Ver 2.0 works for nets and roads, there are two examples. JAstar is for B4j.
 

Attachments

Last edited:

derez

Expert
Licensed User
At the moment version 1.0 works "only" on arrays like the one in the picture, where neighbors are with difference of 1 in x or y or both, so it will not work for roads or similar networks.
I'll keep working on it to find a way for the more general type (I don't want the library to deal with definitions of the net).
 

derez

Expert
Licensed User
It was faster then I expected. Version 1.1 is working by the supply of neighbors from the application and not by distance.
The library now solves the maze in the picture in 100ms on an emulator (including the drawing).
I'll have to check it on roads. Anybody has a database with junctions, distances etc ?
 

Attachments

Last edited:

derez

Expert
Licensed User
While working on a roads network testing I found many problems in the published version. It works well but the found route may be slightly longer than the shortest route.
I'll learn some more and then update, be patient...
 

Informatix

Expert
Licensed User
Just to mention it: if someone needs an optimized version of the A* algorithm, e.g. for game needs, there's one in my Steering behavior library. I spent time to make it as fast as possible, that's why it's only available in the donationware version. And that works also for roads.
 
  • Like
Reactions: eps

peacemaker

Well-Known Member
Licensed User
Strange that first not ideal version is not published :-(
 

peacemaker

Well-Known Member
Licensed User
I meant that this topic for a library actually is without any lib.
 

derez

Expert
Licensed User
I had intention to publish it but found that it is redundant, so cancelled the publishing. Read post #6 above.
 

peacemaker

Well-Known Member
Licensed User
I just meant that if topic exists about some lib - why it's useless.
OK, subject is interesting, but nothing to discuss about...
 
Last edited:

Informatix

Expert
Licensed User
I had intention to publish it but found that it is redundant, so cancelled the publishing. Read post #6 above.
Note that the full version of my library is not free, so there is some interest to post here a free version of the A* algo. Only people needing a very optimized version should have a look to my library.
 

peacemaker

Well-Known Member
Licensed User
Here also a free simple version can be for test, and Pro paid version promised\described from the topic starter.
 

derez

Expert
Licensed User
I've got Informatix's permission to publish the library so you can download it from the first post.
 
Top