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.

 

[wonder]

Good job!! Very useful lib!!

 

[derez]

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]

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 ?

 

[derez]

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]

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.

 

[derez]

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.

 

[peacemaker]

Strange that first not ideal version is not published :-(

 

[derez]

Strange that first not ideal version is not published :-(

You can use informatix Steering behavior library.

 

[peacemaker]

I meant that this topic for a library actually is without any lib.

 

[derez]

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

 

[peacemaker]

I just meant that if topic exists about some lib - why it's useless.
OK, subject is interesting, but nothing to discuss about...

 

[Informatix]

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]

Here also a free simple version can be for test, and Pro paid version promised\described from the topic starter.

 

[derez]

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