Artificial Intelligence - Bot path finding

[Toady]

@kirby - Thank you

@Secure - Well I wouldnt go there hehe Thank you.

UPDATE:

Added an example in the source code to help people get started very easily. I also got rid of that pop up box displaying the time and put the time in the gui instead.

I improved speed by ~20%. Good right? hope so.

[James]

I would. AI as I know from when I programmed some small games in a different language was hard work, although you make it seem easy.

20% more speed? WOW.

[Toady]

I would. AI as I know from when I programmed some small games in a different language was hard work, although you make it seem easy.

20% more speed? WOW.

Yes, I optimized a part of the algorithm that was part of the searching.

[Aces]

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.

kuk-bot creator uses this for mm.BOT baal/meph/andy bots on diablo 2

[Toady]

kuk-bot creator uses this for mm.BOT baal/meph/andy bots on diablo 2

I wouldn't doubt it, diablo 2 is a good example for this being used.

[JavaCupiX]

Another interesting technique exists in finding paths and maybe faster depending of the situation:

Begining : You created a 2 dimensionnal matrix of the field where the start position equals 1, the end position equals -2, every "wall position" is -1 and every "free position" is 0

Main :

Loop through the matrix positions

If you hit the a position wich value is greater than 0 then add the value of the current position + 1 to all the surrounding fields equal to 0

If you hit -1 don't do anything

If you hit -2 check if any surrounding field is greater than 0, if this is true a path has been found, to get the path you just follow the decreasing values until you hit the 1 value

This is a good exercice to practice basic pathfinding, you can even add constraints like sand, mud by adapting the basic algorithm...

[Toady]

Another interesting technique exists in finding paths and maybe faster depending of the situation:

Begining : You created a 2 dimensionnal matrix of the field where the start position equals 1, the end position equals -2, every "wall position" is -1 and every "free position" is 0

Main :

Loop through the matrix positions

If you hit the a position wich value is greater than 0 then add the value of the current position + 1 to all the surrounding fields equal to 0

If you hit -1 don't do anything

If you hit -2 check if any surrounding field is greater than 0, if this is true a path has been found, to get the path you just follow the decreasing values until you hit the 1 value

This is a good exercice to practice basic pathfinding, you can even add constraints like sand, mud by adapting the basic algorithm...

Is this going to get you the shortest path with the least amount of energy and the least amount of nodes searched? I doubt it from the way you described it. This might work well for none maze like matricies with small amount of nodes to check. Sounds like a good idea though.

[JavaCupiX]

Is this going to get you the shortest path with the least amount of energy and the least amount of nodes searched? I doubt it from the way you described it. This might work well for none maze like matricies with small amount of nodes to check. Sounds like a good idea though.

Yes it finds the fastest path to the maze though in my example it doesnt take the "least energy", we used to study pathfinding and compared the topic way and this way described here... They all had their weak & strong points... I will try to post the autoit code to my algo so you can compare/understand it

[Toady]

Yes it finds the fastest path to the maze though in my example it doesnt take the "least energy", we used to study pathfinding and compared the topic way and this way described here... They all had their weak & strong points... I will try to post the autoit code to my algo so you can compare/understand it

k sounds cool

[Toady]

UPDATE

Openlist is now a priority queue. This speeds up the searching dramatically. You will notice a difference between this and the last version.

[Toady]

UPDATE

Added option to make the bot move diagonal if needed. The bot will not cut around corners, the bot moves in a smooth more human-like manor.

Searching nodes is animated now. You can see how the bot searches for the path node by node.

[James]

Dude, this is amazing! You just astound me everytime.

[Toady]

Dude, this is amazing! You just astound me everytime.

thx! now make a game out of this lol

[jokke]

I love what you have done with this!! Great Work!!

I have to admit iwe not read the souce and dont know how you work out you'r "magic", but i still wounder how you determine the path, do you use connections, or do you use hinders ?

Edited June 16, 2007 by jokke

[Mast3rpyr0]

Thats awesome. wish i had the time to go through the code, i bet i could write a game after reading it.

[fisofo]

nicely done Toady... I remember studying A* when I was in college, you've optimized it quite nicely!

Now I'm just waiting to hear of someone becoming a programming prof at a university teaching AutoIt Your example will be something like chapter 15, "A* searching and AutoIt"

Shoot, I'd teach it, anyone want to pay my tenure?

[idusy]

Found a little flaw.

When searching for a path down a column, it skips a row each time, meaning when there's a path it could take, it skips over it

The first takes 28 nodes, second only 26 on a path the first could have taken.

That is, it's a flaw if the objective of the program is to find the absolute shortest path to the goal.

Edited June 16, 2007 by idusy

[Toady]

Fixed, I forgot to change something back in my code after the last version. The priority queue was inserting values in places it shouldn't.

Edited June 17, 2007 by Toady

[Toady]

I love what you have done with this!! Great Work!!

I have to admit iwe not read the souce and dont know how you work out you'r "magic", but i still wounder how you determine the path, do you use connections, or do you use hinders ?

As the search progresses each node points back to its parent node. The node with the lowest F cost is chosen to be the the current node.

F = G + H

where G is the cost of the path from the starting node to the current node. Each node has its own weight to be added to G, a blank space has a weight of 1, sand = 2, water = 3, and hill = 4. So trying to walk across a hill is like walking 5 moves. Thats why the bot will find it easier to just go around the hill.

H is the heuristic cost from the current node to the goal node. Two H heuristics can be selected, one is Manhattan and the other is Euclidean. Manhattan will cause the path to be in a L shape while Euclidean causes the path to be in a zigzag.

Edited June 17, 2007 by Toady

[nfwu]

Some pointers:

Overestimating Heuristic Cost:

Using a heuristic that routinely overestimates (the distance cost) by a little usually results in faster searches with reasonable paths.

If making the world bigger you could decouple the path finding data from the search space.

This would reduce memory consumption.

#)