Jump to content

  • Log In with Google      Sign In   
  • Create Account

A* advices


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Aurioch   Crossbones+   -  Reputation: 1304

Like
0Likes
Like

Posted 11 May 2013 - 11:52 AM

Hello

 

I'm still working on AI for my game, however I'm getting close. After 2 completely failed attempts and 1 semi-decent attempt I finally wrote that works as intended which I am happy with. However, there are 2 problems I'm currently trying to solve:

  • AI is still blind for map changes until it recalculates the path

  • Enemies cannot avoid each other if they need to pass through same node

I'm using 15*15 square grid with no diagonal movement, single region.

I've come up with several possible solutions which are (or at least should be) fairly easy to implement, however I'm not pleased with either of them. I've also checked multiple sources on internet about A* but either there wasn't much useful stuff or I'm still too stupid (or "inexperienced") to figure out proper solution from material I found.

 

While I'm trying to figure out proper solution, I'd like an opinion of more experienced people on solutions listed below and code provided, or maybe some other ideas I could try.

 

1) Perform only several steps with each update while taking other enemies into account

This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.

 

2) Update path when collision with other unit is detected

This "feels" more like a band aid rather than valid solution. It helps resolving stucked enemies but does not fix the problems. Impossible if there are 2 parts of the map connected only with one 1 tile wide path.

 

3) Recalculate path each Update when possible

I tried it... just now. Enemies started dancing between 2 nodes - I assume there is the path of equivalent cost from both those nodes.

 

4) Recalculate path when 2 enemies are going to step on same node

Sounds nice, however also suffers with "choke" problem.

 

AI code:

Spoiler

 

Pathfinding code:

Spoiler

 

Maybe I could work on art a little until I figure out proper solution... XD

 

Thanks in advance smile.png



Sponsor:

#2 VladR   Members   -  Reputation: 722

Like
0Likes
Like

Posted 11 May 2013 - 02:43 PM

It helps resolving stucked enemies but does not fix the problems. Impossible if there are 2 parts of the map connected only with one 1 tile wide path.

First of all, it looks like you need to start taking into account 1-block-wide paths that can block everyone else. That alone will take care of majority of the artifacts you are experiencing.

 

 

You need to keep track, in a separate array, which blocks (e.g. bridges/tunnels/roads) are those potential blockers. And when these blocks are a part of some other enemy's path, you simple adjust the path of the unit to stop at the first block near the start/end of the bridge/tunnel/road that won't block anyone. Keep a separate FSM state for those enemies, so you can easily track them later when the path becomes clear again.

 

 

There have been numerous RTS games where you could actually see this, when someone was crossing the bridge, that all other units started to mess around (e.g. masking the fact that they were waiting for the bridge to be cleared).


VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

 


#3 VladR   Members   -  Reputation: 722

Like
1Likes
Like

Posted 11 May 2013 - 02:50 PM


1) Perform only several steps with each update while taking other enemies into account

This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.

You seem to be missing the point. You won't actually detect the full path (or even if it is possible to get there) until you actually went though all open/closed blocks. How many frames will it take - that depends on the number of blocks you check each frame vs number of all blocks. if you check 5 blocks each frame (for each unit) and you need to check 100 blocks to come up with full path, then it takes 100/5 = 20 frames to come up with full path - and that is OK.

 

All, that you really want to do, is just to give the player an illusion of instant pathfinding (even if it takes up to a second to come up with full path).

If your initial estimate was wrong, well that's OK. You never played an RTS where you give few units a command and they suddenly change their direction after a second ?

 

This is why it takes so long in those RTS games to finish the initial rotation towards the correct direction. While they are rotating, they're giving the player an illusion that they know where to go, even though, for a fact, they still don't.


VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

 


#4 Aurioch   Crossbones+   -  Reputation: 1304

Like
0Likes
Like

Posted 14 May 2013 - 10:00 AM

I indeed completely missed the point of partial pathfinding, thanks for pointing that out >.<

 

Also, thanks for advices, I'll keep em in mind for future projects; unfortunately, I'm not working on RTS (far too complicated project for me right now) but on something far simpler. I'll try to figure something out; maybe I could look again at the original game (Namco's Battle City)...

 

Or maybe I'm overcomplicating things, which wouldn't suprise me.

 

About your examples, thanks for reminding me of "stupidity" of Dragoons from StarCraft XD

 

EDIT: While we're talking about RTS games, how does pathfinding know when to stop moving units if destination is unavaiable? For example, units in StarCraft will try to get to the target until you stop them while in other RTS they'll come as close as they can to target and then stop.


Edited by Aurioch, 14 May 2013 - 10:11 AM.


#5 BeerNutts   Crossbones+   -  Reputation: 2999

Like
0Likes
Like

Posted 14 May 2013 - 02:40 PM

FWIW, I would do this:

 

Calculate the path, regardless where the enemies are in the world:

#1, when the Map changes (ie, a wall is built), check if an AI's path will cross that tile, if so, re-calculate for that AI.

 

For intersecting Enemies, that can be tough:

What if 2 AI are moving in opposite directions, and their path's occupy the same line of tiles, but in opposite directions?  One solution would be to move one AI off a tile for a few frames, then move him back when the other AI is clear.  Either way, you'll have to do something before the point of collision between the 2 AI.


My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS