Jump to content
  • Advertisement
Sign in to follow this  
ID Merlin

AI and Zone of Control

This topic is 3796 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I had an AI routine that wasn't performing well at all. I traced it to the system trying to move into the midst of the enemy formation. The units couldn't get there because the hex was surrounded by zone of control hexes, which stop movement. I resolved that problem by building a zone of control map along with the influence map, which works pretty well. There is a potential pathological case though. If the enemy units are in a circle, or spread out, there could be "holes" where there is no zone of control, but these hexes will be blocked to movement because they are surrounded by blocked hexes. Does anyone know of an algorithm that would run fairly quickly to catch these holes, so they can be marked as blocked?

Share this post


Link to post
Share on other sites
Advertisement
tbh im a bit of a noob at programming, but thinking logically, could you not define the area by getting the position of the outer hexes and doing an area equation. And then have a function that tests if a hex is in that area and then if it returns true to have it blocked?

I have no idea what the code for that would be but yea. Just an idea ;)

Share this post


Link to post
Share on other sites
I think all you've done with the zone of control map is moved the problem, rather than solving it. Surely there is an implicit zone of control map already, as that is what is stopping you reaching these locations with the original search. Making it explicit presumably just lowers the granularity or something.

I don't know of an efficient way to find these circles. I'm not sure it can be done efficiently unless the number of units involved is always small. If units maintain a list of other units near to them then it may be possible though.

If these circles are generally small, just try pathfinding from the destination back to the source instead of the other way. Or, abort your normal search when the best solution so far is more than X times the initial estimated distance, where X might be something like 2 or 3.

Share this post


Link to post
Share on other sites
Reversing the path finding will help a lot. Thanks for the suggestion.

The original problem was caused by trying to develop a "front" line, but sometimes it intersected the enemy zone of control. I ditched that for the time being while I work on fixing that problem.

Share this post


Link to post
Share on other sites
If you have AI Wisdom 1, Steve Woodcock (Ferretman) had a good article on using influence maps to determine fronts, flanks, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
If you have AI Wisdom 1, Steve Woodcock (Ferretman) had a good article on using influence maps to determine fronts, flanks, etc.


I'll have to get that. That is a problem I'm tackling right now. Thank you.

Share this post


Link to post
Share on other sites
If the empty hexes are surrounded by blocked hexes then there is no way to move there. So where's the problem? Maybe I'm just misunderstanding you.

Share this post


Link to post
Share on other sites
The problem is that you can end up examining every single other space on the map to look for a path before the algorithm works out that it's been given an impossible task.

Share this post


Link to post
Share on other sites
Right. I'm working on a preprocessing step that can mark unreachable hexes before I try to use A-Star to find a path.

I can preprocess hexes by counting surrounding hexes with zone of control. If there are six, I mark the hex as unreachable. This fails when the hex isn't surrounded by adjacent zones, but IS surrounded by a circle of zones. For instance, if there are two adjacent hexes in the center that aren't zoc, but are surrounded, the count will only be five for each of those.

I keep coming back to some sort of flood-fill algorithm, but running that on the whole map would seem to be rather slow. Or, some variant of a convex hull might work. I am hoping for something faster and cleverer, I guess.

Share this post


Link to post
Share on other sites
If it's a hex based game, then I assume you're trying to do 60 fps. In which case a flood fill of even a 100 by 100 map is unlikely to cause any noticable performance blip.
You could use the positions of friendly units as the start for the flood fill. Once you've done the first one, most of the others will already be on hexes marked as reachable, so no need to do any more work for them

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!