Terrain analysis
Author
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
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.importanceThen 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.
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
If you're talking about tight-areas (canyons / alleys) you could use a shallow water-shed algorithm to find these types of places.
Will
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 ....
Author
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
greetz
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).
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.
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.
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
- 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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
