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

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

  • Astar.png
    Astar.png
    43.2 KB · Views: 291
  • Astar.zip
    6.4 KB · Views: 241
  • roads.zip
    460.3 KB · Views: 254
  • AStar_example.zip
    7.1 KB · Views: 242
  • roads.png
    roads.png
    452.5 KB · Views: 249
  • JAStar2.zip
    6.4 KB · Views: 235
Last edited:

derez

Expert
Licensed User
Longtime 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
Longtime 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

  • Maze.png
    Maze.png
    45.2 KB · Views: 245
Last edited:

derez

Expert
Licensed User
Longtime 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
Longtime 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

derez

Expert
Licensed User
Longtime User
Informatix said:
it's only available in the donationware version
I've done my homework and version 2.0 now works for both roads and matrix, but it will not be published.
 

Attachments

  • roads_demo.png
    roads_demo.png
    275 KB · Views: 211
  • Matrix_demo.png
    Matrix_demo.png
    48.3 KB · Views: 206
Last edited:

peacemaker

Expert
Licensed User
Longtime User
Strange that first not ideal version is not published :-(
 

peacemaker

Expert
Licensed User
Longtime User
I meant that this topic for a library actually is without any lib.
 

derez

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

peacemaker

Expert
Licensed User
Longtime 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:

peacemaker

Expert
Licensed User
Longtime 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
Longtime User
I've got Informatix's permission to publish the library so you can download it from the first post.
 
Top