134 replies to this topic

[Toady]

A * Searching Algorithm - Pronounced "A star"

UPDATED: May 21, 2008

A bot path searching algorithm that will find the shortest and least cost path to the final state (goal). I wrote an example to visually explain how this is used in the real world. This type of bot searching is commonly used in games that are based on a grid system. The images below are taken from the example program that you can get below this description.

For example, say we have a map of some terrain. Shown below.



The bot must reach the goal with the shortest distance possible (if the path exists). The bot must also take into account different terrain types, each of them have their own difficulty level of traveling. The easiest type of terrain to move on is flat ground, so the bot will choose this over any other. The difficulty levels are ordered from easiest to hardest below.

Easy - Flat ground
Medium - Sand
Hard - Water
Very Hard - Hill

The bot then searches all possible nodes, only searching those that are the easiest to travel on as well as those closest to the goal. Below shows the nodes that the bot searches denoted with a yellow block "SN". Note that not all the nodes on the grid are searched, that is why this algorithm is so fast.



The bot then calculates the shortest and easiest path to get to the goal only using those searched nodes. Below is the path the bot takes.



NOTE RULES:
1. There must be a Start and a Goal.
2. The path does not have to exist.

Here is a screen shot of the program that lets you play around with it for fun.
Below is a GUI example that lets you see how this works. Download the script below the screen shot.

Attached Files

•  A_Star.au3   25.25K   1531 downloads

Edited by Toady, 21 May 2008 - 05:43 PM.

[ConsultingJoe]

Very cool looking, I have't tested it but it could be used in a game

[ofLight]

Very Cool Toady, like most of your other scripts, Cant Wait to try this one out \:D/

[James]

Wow, this looks awesome. AI, in AutoIt whats next?

[ConsultingJoe]

If you add a third demention to this, and we use the openGL plugin. we can make a nice 3D maze game.

[Obi-w00t]

Wow that's pretty cool! I've made a start on a very simple neural network in AutoIt (logic gate functionality) to get another kind of learning-AI. I have some good resources on neural networks if you want to further pursue artificial intelligence in AutoIt

[Toady]

Cool, glad you all think this is interesting. I had to write this same thing in C# for a graduate class I took last semester. Thought I'd write it in autoit for fun

@Cyber - Yes this is possible, would be neat to do this. The search space would be huge lol.
@Obi-woot - I would be interested in seeing what you have done

[James]

3D Space? Awesome

[CoderDunn]

I couldn't help myself since this is so cool so I had to make a GUI example. With my script you can "paint" a map then test it. To "paint" a tile, select the type at the bottom then click where you want it on the grid. The same rules apply ... you must have a solid wall (black) border around the parameter of the map. It works great otherwise.

Here is the script:


And here is a screenshot of it making it's way through a map:


Hallman

Edited by Hallman, 05 June 2007 - 10:20 PM.

[Toady]

I couldn't help myself since this is so cool so I had to make a GUI example. With my script you can "paint" a map then test it. To "paint" a tile, select the type at the bottom then click where you want it on the grid. The same rules apply ... you must have a solid wall (black) border around the parameter of the map. It works great otherwise.


Hallman

Nice, I was just in the process of creating this lol. I appreciate you adding this gui! Makes this whole thing more fun
The simulation feature is awesome!

Edited by Toady, 05 June 2007 - 10:42 PM.

[CoderDunn]

Nice, I was just in the process of creating this lol. I appreciate you adding this gui! Makes this whole thing more fun
The simulation feature is awesome!

No problem. It seems to lag if you make the whole inside white with no blocks and put the start and goal at either end. It shouldn't take so long to path this since there is nothing in the way. A bug maybe?

Hallman

Edited by Hallman, 05 June 2007 - 11:12 PM.

[Toady]

No problem. It seems to lag if you make the whole inside white with no blocks and put the start and goal at either end. It shouldn't take so long to path this since there is nothing in the way. A bug maybe?

Hallman

This is no bug, the algorithm works on a search space. Meaning that nodes are being moved around from list to list until the goal is in the closed list or the open list is empty. Almost but not all nodes are being used in the search space. There are other methods to make the searching faster, yet it involves pointers and sorting the open list. I can make this somewhat faster if I sorted the open list by each nodes F cost and pull from the top of the stack.
This is done using autoit, which we know is not all that fast in comparison to c language.

Another note is that A Star searching will find the shortest path possible if it exist, making this admissible. This is the advantage.

For now I suppose having the GUI buttons go inactive and display a message saying its being calculated. I will work on speeding this up.

Edited by Toady, 05 June 2007 - 11:33 PM.

[jokke]

How much time would it take to calculate the path where the grid is X 500+, Y 500+ length of walk atleast 50+ nodes, and pathed nodes are atleast
400 nodes. mather of ms or secounds?

[Toady]

How much time would it take to calculate the path where the grid is X 500+, Y 500+ length of walk atleast 50+ nodes, and pathed nodes are atleast
400 nodes. mather of ms or secounds?

That depends on many factors. If its just a series of skinny paths then it will complete within a couple milliseconds. If the paths are large open areas then it will take a few seconds because the bot will need to check more useless nodes. Overall if you were to create a huge maze using only skinny hallways, the bot will find the goal really fast. Thus if you made one huge open area then the bot will need a lot more time to think, many more possible moves. Sounds backwards don't it?

The other factor is how this algorithm is coded. Meaning is it using up to much memory? Is the open list a priority queue? Right now im creating node structs. I was thinking about using just string arrays but that will be too many string computations. I am working on making this a lot faster for search spaces that are large.

Anyone up to the challenge? Anyone wanting to optimize this?

[Toady]

Updated - Now Faster!

I optimized this algorithm by making a lot of changes. Now there is less comparisons and less searching. I also modified the GUI example a little to fix everyones confusion they may have.

Edited by Toady, 06 June 2007 - 04:10 PM.

[ConsultingJoe]

I couldn't help myself since this is so cool so I had to make a GUI example. With my script you can "paint" a map then test it. To "paint" a tile, select the type at the bottom then click where you want it on the grid. The same rules apply ... you must have a solid wall (black) border around the parameter of the map. It works great otherwise.

Here is the script:


And here is a screenshot of it making it's way through a map:


Hallman

Very Cool, Error checking needs to be added though.

When I get home for work in at 5:00 Central. I'm going to try that 3d thing, to see if its possible. I don't see why it wouldn't be.

Edited by CyberZeroCool, 06 June 2007 - 04:21 PM.

[james3mg]

Note that the Start and End blocks are poorly placed in the GUI - they're on the edge, requiring that at least two "open" (path) blocks be on the edge, and for A* to work, there has to be a complete frame of "walls" (I keep getting "Badly formatted array" errors if I leave the start and goal blocks where they are) - maybe a layer of black blocks needs to be added to the GUI that can't be changed to white (path)?

Edited by james3mg, 06 June 2007 - 05:05 PM.

[Toady]

Note that the Start and End blocks are poorly placed in the GUI - they're on the edge, requiring that at least two "open" (path) blocks be on the edge, and for A* to work, there has to be a complete frame of "walls" (I keep getting "Badly formatted array" errors if I leave the start and goal blocks where they are) - maybe a layer of black blocks needs to be added to the GUI that can't be changed to white (path)?

Yes they are in a bad place, I will update the gui to fix this. This badly formatted array is caused from the searching going out of bounds. Ease fix.

[poisonkiller]

Hallman, I'm having some trouble with your script. When I clear every wall square and and press "Go!" then SciTe gives me this error:

C:\Pathing_GUI_TEST.au3 (358) : ==> Array variable subscript badly formatted.: 
If DllStructGetData($data[$x][$y-1],"value") <> "x" And Not _IsInClosedList($closedlist,$data[$x][$y-1]) And Not _IsInOpenList($openlist,$data[$x][$y-1]) Then 
If DllStructGetData($data[$x][^ ERROR
->22:56:15 AutoIT3.exe ended.rc:1

Am I doing something wrong?

EDIT: Just tested it, this error comes every time, when I make only one path for it to find or delete every wall square.

Edited by poisonkiller, 06 June 2007 - 08:00 PM.

[james3mg]

Hallman, I'm having some trouble with your script. When I clear every wall square and and press "Go!" then SciTe gives me this error:

C:\Pathing_GUI_TEST.au3 (358) : ==> Array variable subscript badly formatted.: 
If DllStructGetData($data[$x][$y-1],"value") <> "x" And Not _IsInClosedList($closedlist,$data[$x][$y-1]) And Not _IsInOpenList($openlist,$data[$x][$y-1]) Then 
If DllStructGetData($data[$x][^ ERROR
->22:56:15 AutoIT3.exe ended.rc:1

Am I doing something wrong?

See the previous two posts - you have to leave every single outer square as a wall, which also requires that you move the start and goal out of the corners they start in so those squares can be walls as well.