Jump to content
  • Advertisement
Sign in to follow this  

Terrain analysis

This topic is 4828 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

Hey, I'm looking for a decent algorithm that can detect choke points in the terrain, and especially choke points through where the enemy is likely to attack. All help will be appreciated. greetz

Share this post


Link to post
Share on other sites
Advertisement

for all discrete positions on map:
initialise position.importance to zero

while not bored:
pick random position A on map
pick random position B on map
plot Route from A to B
for each position along Route:
increment position.importance


Then you have an importance value for each part of the map showing how likely it is that a unit will have to pass through there.

If this has to be made more specific to deal with attacks and so on, alter the functions that choose the positions. For example, the first position could be randomly chosen as an area near or in their base, the second position could be constrained to an area near or in yours.

Share this post


Link to post
Share on other sites
Can you pre-compute this, or is it real time? Do you have a definition of choke-point for you app?

If you're talking about tight-areas (canyons / alleys) you could use a shallow water-shed algorithm to find these types of places.

Will

Share this post


Link to post
Share on other sites
How do you model that units can climb up then ? Definitely it's for precomputation I think. Thus even if it takes one hour per map to compute ....

Share this post


Link to post
Share on other sites
It's real-time, units can not climb up or go down. With choke points I mean narrow areas where the enemy is vulnerable when traveling, in other words, areas that are easy to defend when the enemy attacks, like bridges or narrow passages between trees or cliffs.

greetz

Share this post


Link to post
Share on other sites
Quote:
Original post by lamlam
Hey,

I'm looking for a decent algorithm that can detect choke points in the terrain, and especially choke points through where the enemy is likely to attack.
All help will be appreciated.

greetz




An A* pathfinder used on a bunch of random endpoints on the map (Monte Carlo method...). Keep track of the paths and find the sections that have the highest path density (these are usually choke points).

I saw a A* demo program once that ran 500 test paths on a 256x256 map (with traversal difficulty for each point) which graphicly showed all the accumulated paths. (It did a good coverage of the map.)
I thought - hmm that could be used to identify center point data for the Coarse level of a hierarchical path finder.......

You could probably preprocess the map to lower the granularity (averaging tiles together to lower the map size) before using the A* on it.
This would speed it up quite a bit.

Remember you can spread the processing across several turns if it eats alot of CPU and you intend to use in to recalculate a dynamic map (where player placed objects can cause new blockages).


EDIT- You could probably optimize it alot by placing one of the two points at the game assets that are targets and also limiting the distance from there to the other random endpoint (no need to go across the whole map).




Share this post


Link to post
Share on other sites
Have you listen about flooding algorithm? Or about road ambush algorithms?
You might use them.

If you know how look the ideal position, you could just search for them. Try to write a simple pattern matching algorithm and apply it on you program.

Share this post


Link to post
Share on other sites
From my collection of on-line papers (www.cgf-ai.com/links.html), check out:
- AI getting a grasp of geography, Marc Everson
- Determining possible avenues of approach using ANTS, Svenson, Sidenbladh
- Realistic Evaluation of Terrain by Intelligent Natural Agents (RETINA), René Burgess

Some of the other papers might be helpful as well.

William

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!