Deviant Login Shop  Join deviantART for FREE Take the Tour
×



Details

Submitted on
December 4, 2013
Image Size
8.9 KB
Resolution
540×600
Link
Thumb
Embed

Stats

Views
907
Favourites
21 (who?)
Comments
104
Downloads
28
×
~Game Path Solver~

**This is not a game - this demonstrates the A* method used in games to find the best path to reach a location in a map.

Have you ever wondered how game characters find their way to locations? If they just went in a straight line, they would eventually get stuck on walls. Well, actually in many games they do just that! LOL

But in computer science, nearly everything has already been solved and there is a best solution available. When it comes to finding paths through obstacles, the solution is a method called A* (A-Star). Not only A* always finds a path, but assuming a valid one exists, it will also find the shortest one.

In this simulation, the character is the red circle, and you can click to tell it to go anywhere in the white area. Black blocks are walls. The character will use A* to find the shortest possible way, and also show you how many steps it took to get there. If the area cannot be reached, it will not go.

Every time you run this it will create a new random map, but you can SHIFT-CLICK to edit it anyway you like. :D

You may be asking: if A* is the best path solver, then why do my game characters sometimes end up stuck on walls? The answer to that is performance. Real time 3D games use so much computer resources just to display the 3D world that it may not be able to afford the additional processing power and memory required by A* for every single character walking in the game.

They will then use "cheaper" path finding solutions for the sake of performance, that are not as smart as A*, but will give faster (yet inaccurate) results using less processor and memory. That's how we end up with stupid game characters getting stuck running against walls! You can try all you want here - for as long as there is a viable way, it finds the best path instantly and will *NEVER* get stuck on walls. Some of the best RTS games use A* to move the troops in the game maps. ^_______^

A* finds the shortest path as fast as you can click the map, and it's flexible enough to allow you to change your mind in the middle of a path. It will then find a new path starting from where you are at the moment.

I am creating a new tank game and will use A* to drive the enemy tanks, so if they can see you, they will chase your quite efficiently. I have also used A* to drive the artificial intelligence of the monsters in my "Monster Maze" game (below), where there are as many as 50 monsters using A* at the same time in the highest level. :D

-Maze Monsters- by ken1171

This program was written in ActionScript 3.0 using freeware FlashDevelp. Hope you like it and thanks for coming by!
Add a Comment:
 
:icongraenfur:
Graenfur Featured By Owner Dec 18, 2013
Hey, about your tank collision problem: I'm not any kind of expert here and I don't know how exactly things are done in your game, but you could "record" each tanks movement in an array or something.. So when tank runs into problem like being stuck (which of course would need to be defined what is and isn't stuck) then it travels back in the recorded path until it is unstuck again..
[or the problem is exactly the detecting weather it is or isn't stuck?]
Anyway.. I dunno.. just a suggestion.
Reply
:iconken1171:
ken1171 Featured By Owner Dec 18, 2013  Professional Digital Artist
Hey, that idea might actually work! :D  The way I am doing it now is to only record the last known position before a collision has happened, and then return the tank there. But 1-step recovery is not being enough. If instead I keep an array of previous positions before a collision, there will be a better chance of recovering from getting stuck on the walls.  I can keep only, say, the last 5 positions, and then try them in reverse order until there is no more collision. I will see if that works! ^_____^
Reply
:icongraenfur:
Graenfur Featured By Owner Dec 20, 2013
I remember working with box2d and there was this 'bullet' property which could be assigned to fast objects so they would checked for collisions more often than others. While my idea is not the same, it made me figure that more detailed info about latest positions may help here.
Let me know how it works out.

Also looking forward to that game. [:
Reply
:iconken1171:
ken1171 Featured By Owner Dec 20, 2013  Professional Digital Artist
I actually solved 95% of the wall-sticking collisions with a rather simple method - just undo the last action before the collision. Simple is always better! :D  Designing levels for the game now. ^^
Reply
:icongraenfur:
Graenfur Featured By Owner Dec 21, 2013
Hmm. Isn't going backwards through recorded positions the same undoing? :D
Reply
:iconken1171:
ken1171 Featured By Owner Dec 21, 2013  Professional Digital Artist
Not really, because I only need to remember the last action before testing for collision, and if the vehicle hits something, all I have to do is to revert that action. I still have rare cases of getting stuck on the walls, but I am happy enough it's rare now.

The tanks now have better graphics, increased rate of fire, and yesterday I have completed 5 levels for the game. Just have to decide what happens when we win.
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 8, 2013
Epic man! :)
Good ol' pathfinding. I really wish I had the time to work on programming. I feel like I could be really good at game making if I just has an extra hour each day... lol
Reply
:iconken1171:
ken1171 Featured By Owner Dec 8, 2013  Professional Digital Artist
Thank you! I am still trying to find a way to avoid getting my tank stuck on the walls because of poor collision detection. I try to pull it back to where it was right before collision, but that doesn't seem to be enough... >___<
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 9, 2013
Oh! I've ran into that one before!
It was a while back, and I don't think I solved it...Sweating a little...  
Reply
:iconken1171:
ken1171 Featured By Owner Dec 9, 2013  Professional Digital Artist
This is a pretty common thing, so I am sure there is a solution somewhere. The problem is that my tank not only moves, but it also turns around like a real tank would move. So collision can happen even when it is just turning in place.
Reply
Add a Comment: