Sign in to follow this  
ncsu121978

AI, prevent enemies from running on top of each other

Recommended Posts

Well AI is by far the weakest area of my programming abilities but I do my best.

My question is how do I prevent enemy AI (who are usually chasing the player) from just merging ontop of each other in their pursuit?

The game is 2D top down, there are walls and rooms and doors (open or closed). there are tiles representing the walls but that is all, all movement is free from tile based restriction (save for the walls).

right now i am just randomly spawning mobs in the area to chase the player but I have nothing in place to prevent them from running on top of each other meaning their graphics overlap.

i was thinking on just running the update to figure out where it wants to be at this frame, and as long as it doesnt collide with another mob, then let if move to that location otherwise have it stay in place. but this would prevent say a mob from getting to a different side of the player if a mob is already at the side they are coming from.
For example say there are two mobs approaching the player from the left. Using the above method, when the first mob gets there it will stop, causing the second mob to "run into it" and stop as well. I am not sure how to make it intelligent enough to go around this mob and attack the player from a different direction.

someone please point me in the right direction to correct this behavior.

Share this post


Link to post
Share on other sites
Can your MOBs pathfind away (or around) from walls/doors? If so, consider turning all the other MOBs into obstacles right before you move the first MOB, then repeat for all the other MOBs as they move. Be careful though, this can easily turn into an O(n^2) algorithm if you aren't careful.

Share this post


Link to post
Share on other sites
@Steve_Segreto: yes my mobs can pathfind, so i guess i could treat all the other mobs as obstacles BUT, all of the mobs are constantly moving, as well as the player. so if i compute a path to the player, the next time the player moves that path really isnt leading to the player anymore and would have to be recomputer. Which means we are talking about recomputing a path to the player for each mob every frame and if you have lots of mobs, then that is lots of computation. too much i think.

and about the flocking...not sure how to get it to work in rooms, with cooridors and possibly doors and such. seems like the algorithms are generally using vectors directly towards the player which wouldnt work if there is a wall in the way, or if they are on the other side of the screen, in another room.

Share this post


Link to post
Share on other sites
Quote:
Original post by ncsu121978
and about the flocking...not sure how to get it to work in rooms, with cooridors and possibly doors and such. seems like the algorithms are generally using vectors directly towards the player which wouldnt work if there is a wall in the way, or if they are on the other side of the screen, in another room.

In that same link scroll down to queuing. That's the name for it. You can probably find more information using that term.

Share this post


Link to post
Share on other sites
Quote:
Original post by ncsu121978
Which means we are talking about recomputing a path to the player for each mob every frame and if you have lots of mobs, then that is lots of computation. too much i think.


Don't think. Measure! When it comes down to performance, code and algorithm optimization etc. you should not trust yourself, or at least be aware that your guess is, well, just an inaccurate guess. You will be surprised when you actually test and measure such "slow" approaches. :)

Usually you do not have to recompute everything, just the parts which changed "enough". Do you think that you could store some of the already computed data and work on the altered data? Do you think that you could do the computation for half of the mobs every fifth frame etc? One thing you can be sure: There's always room for improvement. And more often than not, seemingly slow code is doing redudant stuff like recomputing values which haven't changed/haven't changed enough to make real difference. With clever data structures and possibly slightly altered algorithms you can make huge difference.

Do what works best, and if it isn't fast enough, then optimize. But measure first.

Share this post


Link to post
Share on other sites
I agree with Calmatory...

Think of it more like this:

1. Some internal state changes in a particular MOB instance, and it needs to react by selecting a new goal.
2. A MOB chooses a new goal node on the map (maybe this is the same square as the player b/c the MOB wants to attack the player).
3. The MOB charts a path to the goal node and stashes it. It now has a goal and a path to the goal and 0% progress along that path.
4. Now each game turn, the MOB begins advancing along the path towards its goal, keeping track of how far along its path it is (The path can simply be a stack of direction commands like - move north, move north, move east, move south, goal reached... or it can be the actual (x,y) coordinates that need to be visited).
5. If the MOB cannot follow the movement described in the path, because something changed (i.e. another dynamic object blocked the MOBs path), it can recompute the path from its current position to its current goal.
6. If there is no longer a way to reach its current goal, it will need to return to step #1 and select a new goal.
7. If it reaches its goal, it will need to return to step #1 and find a new goal (this may be as simple as "start attacking").

Again be sure to implement and measure before saying something is "too expensive". If you use hierarchical A* and optimize for a 2-d grid such that there are no dynamic allocates/de-allocates, you can get *EXCELLENT* performance. I've had > 1000 MOBs tracking and moving around a 2-d grid at a frame rate of 30Hz on hardware from about 6 years ago, with no problem.

Share this post


Link to post
Share on other sites
using a bulletin board as a communicator between many AI players ...so as to make sure that they are in constant tuch and contact with each other might also ensure that they donot run across each other..one AI player can post on board about its way in the game map(graph) and the other player will respond to it by not following the same path.......it can also enhance the AI level by team work between AI players

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