# Terrain analysis

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

## 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 on other sites
for all discrete positions on map:    initialise position.importance to zerowhile 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 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 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 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 on other sites
Quote:
 Original post by lamlamHey,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 on other sites
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 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

1. 1
Rutin
38
2. 2
3. 3
4. 4
5. 5

• 12
• 15
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633354
• Total Posts
3011493
• ### Who's Online (See full list)

There are no registered users currently online

×