Here's my take on the A* search algorithm - I haven't seen a faster one in DBPro yet, and I'm not finished ...

This post has the library in the source box. The next post will show you how to use it.

It's all set up to allow you to include the library using the 'Files' button in the IDE.

This code shows how to use the library.
There are minimal comments (just on those lines that show how to use the library).

Have a play with it and tell me what you think.

I have a few more search routines to come later too ...

Nice piece of code!

Do you have quite an in-depth tutorial for it IanM? Just for using it for a small project?

Hmmm, I made it as simple to use as I could.

Use 'CreateSearchMap' to create the map. You pass it the dimensions of your grid.

Use 'CreateSearchPathLists' to create one or more paths. to store search results in (they are numbered from zero).

Set up the map using 'SetSearchMap'. Numbers below 1 are walkable, numbers of 1 or greater are blocked.

Call the search routine 'SearchMapAStar8' with a path number, the start coordinates, and the end coordinates. You will get a zero back if no path was found.

You can find the length of the path (number of steps between source and target) using 'SearchPathSize' and passing it your path number, and interrogate each X/Y coordinate by using the 'GetSearchPathX' and 'GetSearchPathY', telling them the path number and the step number you wish to read.


Basically, the source in my second post *is* the tutorial ... however, I could put together something a little more 'meaty' if people really need it ...

As a suggestion, why not modify the move cost to the data inside the SetSearchMap?

This would allow you to make roads (a value of 1) that take a precedence away from cross country (a value of 2) and avoid dense foliage areas (a value of 3). To totally block the map off just give an exponentially high value such as 255.

Worth including ?

Well, yes. That's one of the extra search methods I'm working on at the moment.

But you can't do that with A* - A* works on the principle that you can estimate how far you have to go until you reach the target, and with variable costs, there is no way you can come up with a reasonable estimate.

Anyway, the current method allows you to use the map for more than just searching. For example, it could represent an image number for tiling.

Still, it might be worthwhile separating the the meaning of the one value into two parts - one for cost, one for 'extra' data.

Here is some more example code.

This one generates a random map, with 9 random waypoints and paths 9 bots from point to point.

I've set the sync rate at 10, but try setting it to zero to see how fast my search routine is in real terms ... of course, because the waypoints in this program don't change, the paths could have all been pre-generated for even faster performance ...

Just put this code into a new project, include the library file and then compile and run.

I can't seem to get this to work - i have only DBC v1.12, however I am going to dbpro at end of month, so i try it then.

That's why it doesn't work

Yep, It's fast alright. Even better than the other ones been posted recently.

Maybe have an option of not allowing diagnal paths through walls although diagnal paths across open spaces is ok. Get my drift?

Yes, I tried doing that. Unfortunately, it results in the routine taking 2-3 times as long to run, and the penalty gets worse for bigger maps.

I have just thought of another way of getting the same results that might work though ... I'll report back tomorrow

Here you go Sonic - a restricted A* 8 directional search, that disallows diagonals between blocked cells.

Just add it to the existing library code.

It was fairly easy to add - I misunderstood what you meant yesterday

Ta very much, that's just what I meant. Trouble is I can't think what to do with it right now!

Latest version of the library - Modifications:

- Faster A* searching, due to the inclusion of a heap for the open list.
- Integration of the restricted A*8 search.
- Added A*4 searching.
- Added Flood fill 4 direction searching.

The last one is slower than the others, and you might wonder why I included it. Because of the way it works, it allows you to search from the same source point to multiple targets with the second and later searches virtually free.

Also, I have added a small piece of conditional compilation in this code that allows me to switch in a fast array item swap command within my Array TPC DLL. The gain doesn't seem much (around 4-8%) but on a large map that can be quite a saving.

With the introduction of this, and the heap algorithm, the fastest case of A* has been slightly slowed, but the normal case has been made slightly faster and the worst case has been made massively faster.

The introduction of the heap has also made the A*4 run at a usable speed, so I've also included that too

This is the testbed I've been using, updated for all 4 search algorithms.

1 - A*8
2 - A*8 Restricted diagonal
3 - A*4
4 - Flood 4

The main loop has had quite a change to allow you to see the flood fill search in all it's glory. Press the search key once (4) and you'll see the time it takes (a relatively large amount). Press it again, and you'll see it takes almost no time. Move the target again, and it will still take no time. Move the source, or change the map, and it will need to re-search.

Wow! Excellent stuff Ian

This is where it really benefits DBP being a compiler rather than an interpreter.

Oops, slightly broke the A* stuff. Just replace the function SEARCH_AddToOpenList with this one.

But you can't do that with A* - A* works on the principle that you can estimate how far you have to go until you reach the target, and with variable costs, there is no way you can come up with a reasonable estimate.

Having movement scores would slow the search down because the search routine would need to travel further down the open list more often to find the fastest route, but consequently the algorythm would be useful in more applications.

Critically though the change wouldn't add anything to the search time of the routine if the programmer doesn't make use of the feature.

It's coming - just not in the A* code. I've finished changing that for now.

I'll be adding a variation on the flood4 code that will use costs, and also be adding an 8 direction variation both with and without costs.

If you look at the latest code for A*, you'll see I'm not using a 'list' any more - that's far too computationally expensive to search for lowest values, and the reason that most A* implementations for DB/DBPro are so slow.

I've switched to using a heap that ensures that the lowest value is already at the top.

*EDIT* Also, what does everyone think of building in some visibility data, so that you can't search where you haven't seen? It wouldn't take too much to do this.