Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Code Snippets / Fast A* Search routine

Author
Message
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 1st Jun 2003 22:24
Link
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.
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 1st Jun 2003 22:25
Link
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 ...
Back to top
Profile PM Email Website
D Man
22
Years of Service
User Offline
Joined: 3rd Oct 2002
Location: Germany
Posted: 1st Jun 2003 22:58
Link
Nice piece of code!

God is real, unless declared integer.
Back to top
Profile PM Email
Nilrem
21
Years of Service
User Offline
Joined: 27th Feb 2003
Location: United Kingdom
Posted: 3rd Jun 2003 17:17
Link
Do you have quite an in-depth tutorial for it IanM? Just for using it for a small project?

I hear and I forget. I see and I remember. I do and I understand.
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 3rd Jun 2003 19:24
Link
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 ...
Back to top
Profile PM Email Website
Andy Igoe
22
Years of Service
User Offline
Joined: 6th Oct 2002
Location: United Kingdom
Posted: 3rd Jun 2003 20:10
Link
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 ?

Pneumatic Dryll
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 3rd Jun 2003 21:20
Link
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.
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 3rd Jun 2003 22:50
Link
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.
Back to top
Profile PM Email Website
Red general
22
Years of Service
User Offline
Joined: 19th Nov 2002
Location: United Kingdom
Posted: 3rd Jun 2003 23:19
Link
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.

My computer melts regulary - perhaps it likes being fondue
Back to top
Profile PM Email
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 4th Jun 2003 01:32
Link
That's why it doesn't work
Back to top
Profile PM Email Website
spooky
22
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 4th Jun 2003 02:14
Link
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?

Gronda, Gronda
Back to top
Profile PM Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 4th Jun 2003 02:23
Link
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
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 5th Jun 2003 02:05
Link
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
Back to top
Profile PM Email Website
spooky
22
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 5th Jun 2003 02:46
Link
Ta very much, that's just what I meant. Trouble is I can't think what to do with it right now!

Gronda, Gronda
Back to top
Profile PM Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 6th Jun 2003 01:00
Link
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
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 6th Jun 2003 01:04
Link
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.
Back to top
Profile PM Email Website
Rob K
Retired Moderator
22
Years of Service
User Offline
Joined: 10th Sep 2002
Location: Surrey, United Kingdom
Posted: 6th Jun 2003 01:21
Link
Wow! Excellent stuff Ian

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

Do you want Windows menus in your DBP apps? - Get my plugin: http://snow.prohosting.com/~clone99/downloads/tpc_menus_102.zip
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 7th Jun 2003 21:15
Link
Oops, slightly broke the A* stuff. Just replace the function SEARCH_AddToOpenList with this one.

Back to top
Profile PM Email Website
Andy Igoe
22
Years of Service
User Offline
Joined: 6th Oct 2002
Location: United Kingdom
Posted: 7th Jun 2003 21:30
Link
Quote: "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.

Pneumatic Dryll
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 7th Jun 2003 21:47 Edited at: 7th Jun 2003 21:58
Link
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.
Back to top
Profile PM Email Website
Rob K
Retired Moderator
22
Years of Service
User Offline
Joined: 10th Sep 2002
Location: Surrey, United Kingdom
Posted: 8th Jun 2003 00:50
Link
@IanM - Did you post this in the DBDN CodeBase? (It would be useful if it isn' there)

Do you want Windows menus in your DBP apps? - Get my plugin: http://snow.prohosting.com/~clone99/downloads/tpc_menus_102.zip
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 8th Jun 2003 01:46
Link
I will as soon as I'm happy with what I've got.

I'm considering some heavy changes at the moment - writing a new function for each slightly different system I have just doesn't seem right.
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 10th Jun 2003 21:05
Link
Latest Changes:

A*8 and A*8R searches rolled into a single function
Added a Flood8 and a Flood8R search (in a single function)
Added a new function to enable or disable the restricted diagonal code.
Updated all search functions to allow a 'cost' based cut-off - especially important to restrict the time taken for the flood searches.

I think I'll give this a rest for now ... at least until I need to account for different cost for each cell, or someone convinces me that they really need it

The latest testbed code is in the next post.
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 10th Jun 2003 21:06 Edited at: 10th Jun 2003 21:41
Link
Testbed code

Both now added to Codebase for you Rob
Back to top
Profile PM Email Website
Rob K
Retired Moderator
22
Years of Service
User Offline
Joined: 10th Sep 2002
Location: Surrey, United Kingdom
Posted: 11th Jun 2003 21:57
Link
Excellent. The algorithm will really start to be useful when I start dealing with AI. I am using a memblock matrix so the grid is already nicely defined.

Do you want Windows menus in your DBP apps? - Get my plugin: http://snow.prohosting.com/~clone99/downloads/tpc_menus_102.zip
Back to top
Profile PM Email Website
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 15th Jun 2003 02:04
Link
cool, i could use this for my rts

Back to top
Profile PM Email Website
David T
Retired Moderator
22
Years of Service
User Offline
Joined: 27th Aug 2002
Location: England
Posted: 15th Jun 2003 13:39
Link
IanM, I haven't looked at the code yet but does yours stop the player from going down a dead end? My paths are usually OK but sometimes the player can get lead down a dead end corridor.

You are the th person to view this signature.
Programmers don't die, they just Gosub without return....
Back to top
Profile PM Email Website
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 15th Jun 2003 18:20
Link
Phaelax: Help yourself

David89: You will never get a dead-end from these search routines. They either find a way to the target and populate the path, or won't.
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2024-11-24 03:10:24
Your offset time is: 2024-11-24 03:10:24