Sign in to follow this  
Followers 0
Toady

Artificial Intelligence - Bot path finding

142 posts in this topic

#1 ·  Posted (edited)

A * Searching Algorithm - Pronounced "A star"

 

UPDATED: Dec 1, 2015

 

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.

 

Posted Image

 

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.

 

Posted Image

 

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.

 

Posted Image

 

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.

Posted Image

A_Star.au3

Edited by Toady
Updated to latest version of AutoIt.

www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites



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


[center]AutoIT + Finger Print Reader/Scanner = COOL STUFF -> Check Out Topic![/center][center][font=Arial Black]Check out ConsultingJoe.com[/font][/center][center]My Scripts~~~~~~~~~~~~~~Web Protocol Managing - Simple WiFi Scanner - AutoTunes - Remote PC Control V2 - Audio SpectrascopePie Chart UDF - At&t's TTS - Custom Progress Bar - Windows Media Player Embed[/center]

Share this post


Link to post
Share on other sites

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


There is always a butthead in the crowd, no matter how hard one tries to keep them out.......Volly

Share this post


Link to post
Share on other sites

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


[center]AutoIT + Finger Print Reader/Scanner = COOL STUFF -> Check Out Topic![/center][center][font=Arial Black]Check out ConsultingJoe.com[/font][/center][center]My Scripts~~~~~~~~~~~~~~Web Protocol Managing - Simple WiFi Scanner - AutoTunes - Remote PC Control V2 - Audio SpectrascopePie Chart UDF - At&t's TTS - Custom Progress Bar - Windows Media Player Embed[/center]

Share this post


Link to post
Share on other sites

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 :)

Share this post


Link to post
Share on other sites

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 :)


www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

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

Share this post


Link to post
Share on other sites

#10 ·  Posted (edited)

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

www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

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

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

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

www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

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?


UDF:Crypter a file encrypt / decrypt tool with no need to remember a password again. Based on Caesar cipher using entire ASCII Table.Script's: PixelSearch Helper, quick and simple way to create a PixelSeach.Chatserver - simplified, not so complicated multi-socket server.AutoIT - Firewall, simple example on howto create a firewall with AutoIt.

Share this post


Link to post
Share on other sites

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?


www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

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

www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

#16 ·  Posted (edited)

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

[center]AutoIT + Finger Print Reader/Scanner = COOL STUFF -> Check Out Topic![/center][center][font=Arial Black]Check out ConsultingJoe.com[/font][/center][center]My Scripts~~~~~~~~~~~~~~Web Protocol Managing - Simple WiFi Scanner - AutoTunes - Remote PC Control V2 - Audio SpectrascopePie Chart UDF - At&t's TTS - Custom Progress Bar - Windows Media Player Embed[/center]

Share this post


Link to post
Share on other sites

#17 ·  Posted (edited)

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

"There are 10 types of people in this world - those who can read binary, and those who can't.""We've heard that a million monkeys at a million keyboards could produce the complete works of Shakespeare; now, thanks to the Internet, we know that is not true." ~Robert Wilensky0101101 1001010 1100001 1101101 1100101 1110011 0110011 1001101 10001110000101 0000111 0001000 0001110 0001101 0010010 1010110 0100001 1101110

Share this post


Link to post
Share on other sites

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.


www.itoady.com

A* (A-star) Searching Algorithm - A.I. Artificial Intelligence bot path finding

Share this post


Link to post
Share on other sites

#19 ·  Posted (edited)

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

Share this post


Link to post
Share on other sites

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.

"There are 10 types of people in this world - those who can read binary, and those who can't.""We've heard that a million monkeys at a million keyboards could produce the complete works of Shakespeare; now, thanks to the Internet, we know that is not true." ~Robert Wilensky0101101 1001010 1100001 1101101 1100101 1110011 0110011 1001101 10001110000101 0000111 0001000 0001110 0001101 0010010 1010110 0100001 1101110

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0