I am trying to detect choke points along a path but I am unsure of the best way to achieve one of the steps. What I have so far is the path and the clearance along the path, but am unsure how to detect the narrowing of the clearance in relation to the surrounding area.
For example, In this sketch the x axis is the distance along the path and the y axis is the clearance and I'm trying to detect the red areas: http://i.imgur.com/ZlC5z.png
What might be a good algorithm to detect this?
1
Choke Point Detection
Started by Laccolith, May 06 2011 05:42 AM
11 replies to this topic
Sponsor:
#2 Members - Reputation: 1679
Posted 06 May 2011 - 06:33 AM
look into "mathematical optimization" or "local search", "Hill climbing" for example.
Or simply derivate the curve and look for zeros. Then derivate again where the first derivate are zeros, and if the second derivate is positive (negative???) in those points, you'll have the local minimums.
Or simply derivate the curve and look for zeros. Then derivate again where the first derivate are zeros, and if the second derivate is positive (negative???) in those points, you'll have the local minimums.
#3 Members - Reputation: 958
Posted 06 May 2011 - 09:10 AM
I'd use a (generalized) Voronoi diagram to determine chokepoints. EDIT: Or... something like one. Actually, I'd use a medial axis transform; I'll describe this...
Assign any map tile adjacent to an obstacle a value of 0, any tile adjacent to a"0" a value of 1, any tile adjacent to a "1" a value of 2, etc... These values will propagate across your map like a wave, eventually filling it. You'll also want to propagate the index of the closest obstacle tile, so each tile knows where the closest obstacle to itself is located. Implement the algorithm using an OPEN priority queue like Dijkstra, and what you get is called a Brushfire Algorithm for computing the Distance Transform of the obstacle set (using the Manhattan distance). This can then be used to compute a "skeleton" for your walkable set using a Voronoi-diagram-like construction as follows:
Any group of three adjacent tiles with different "closest obstacle" IDs is a Voronoi vertex. These are connected by "Voronoi edges" as follows: Any pair of adjacent tiles whose "closest obstacle" IDs differ is on a Voronoi edge, and a path of these pairs connecting two Voronoi vertices is the Voronoi edge itself. [EDIT: Whoops; incorrect description; see below.] You get a graph of Voronoi vertices connected by Voronoi edges, and this serves as a good "roadmap" for your environment. (Indeed, you can also do your path-planning on this graph, which is much smaller than the entire tile map.)
*** Here's how I determine edges and vertices:
The method I gave earlier (struck out) works if you have different identifiable obstacles (like points, or convex sets) in a plane; then, Voronoi edges are just the places where regions belonging to different obstacles meet. The problem is that in our case we don't have a clear definition for what constitutes a different obstacle. For instance, if we have a large concave mass of unwalkable tiles that includes a hallway deep into itself, presumably we want an edge running down the center of that hallway. This means that what we really want is the "medial axis" of the walkable set. One way to compute this that I've seen in the literature is to first compute the distance transform (as outlined earlier); then, a vertex occurs wherever there is a local maximum of this function, and vertices are connected by walking along the direction of least change of the distance transform to form edges. Another, which seems simpler and more robust, is to just grow a sphere from each tile until it intersects an obstacle tile; if it intersects two, it's an edge tile, and if it intersects more than two, it's a vertex (but with some experimenting, this latter approach only seems to work in the Euclidean metric).
I used the Manhattan metric. The way I did this was to exploit the information we've been propagating about who the nearest obstacle tile is; I did some experiments, and it works nicely. Here's how the method I used works: For each tile, consider the set of neighboring tiles {SELF, EAST, NORTH}. Then iterate over all 3 pairs of this set, computing distances between corresponding closest-obstacle-tiles. If the sum-of-squares of these distances exceeds a threshold, mark the tile as an "edge" tile. A "vertex" is then just any "edge" tile with more than two 4-connected neighbors who are also edges. This works quite well; I get the following results:
Just so I don't have to edit my post, I'm going to keep calling these vertices and edges "Voronoi" vertices and edges, though in reality the edges are "medial axes," and the graph is called the "shock graph."
Now, along each Voronoi edge (really: edge of shock graph), there is at least one tile whose distance-to-closest-obstacle value is minimal, and you can easily search along the edge to find it. I would call this value the "width" of that edge, and the tile at which it is found the "chokepoint" on that edge.
Once you have these numbers, you can forget about the underlying tile map. You just have a graph (which happens to be a Voronoi diagram, but that's no longer important), with values assigned to the edges. You can identify your base with one or more nodes of the graph (more on this later*), and your opponent's base with another set of nodes. Now what you're looking for, to achieve a defense, is a graph cut that separates you from your opponent. To select the cut, you'd assign a cost to each edge (e.g. a weighted sum of the "width" of the edge, and its distance from your base, though how to select these costs is itself an interesting question**), and then look for a minimum-cost graph cut (where the cost of the cut is the sum of the costs of the edges cut). Once you have this cut, you build a fortification at a chokepoint (as defined earlier) on each cut edge.
* About mapping your base's footprint to the Voronoi diagram: The Voronoi diagram implicitly defines a "deformation retract" of the environment. If you map your base's footprint through the deformation retract, you'll end up with a "footprint" on the nodes and edges of the Voronoi diagram. In less fancy language, when you first did your brushfire algorithm, you could have kept track of each tile's children; then, for any given tile, you can follow the chain of children until you end up on a Voronoi edge/vertex.
** One thing I haven't considered at all is that, sometimes , you might be willing to "stretch" your empire a little if doing so will allow you to control more resources. Then, you might penalize an edge less, even if it is wide, or a little too far from your base, if choosing to fortify it would keep e.g. a mineral patch within your cut of the graph. You can imagine flood-fill type algorithms that compute edge costs based both on the resources that the corresponding cuts contain, the widths of the edges, and the distance from your base.
Assign any map tile adjacent to an obstacle a value of 0, any tile adjacent to a"0" a value of 1, any tile adjacent to a "1" a value of 2, etc... These values will propagate across your map like a wave, eventually filling it. You'll also want to propagate the index of the closest obstacle tile, so each tile knows where the closest obstacle to itself is located. Implement the algorithm using an OPEN priority queue like Dijkstra, and what you get is called a Brushfire Algorithm for computing the Distance Transform of the obstacle set (using the Manhattan distance). This can then be used to compute a "skeleton" for your walkable set using a Voronoi-diagram-like construction as follows:
*** Here's how I determine edges and vertices:
The method I gave earlier (struck out) works if you have different identifiable obstacles (like points, or convex sets) in a plane; then, Voronoi edges are just the places where regions belonging to different obstacles meet. The problem is that in our case we don't have a clear definition for what constitutes a different obstacle. For instance, if we have a large concave mass of unwalkable tiles that includes a hallway deep into itself, presumably we want an edge running down the center of that hallway. This means that what we really want is the "medial axis" of the walkable set. One way to compute this that I've seen in the literature is to first compute the distance transform (as outlined earlier); then, a vertex occurs wherever there is a local maximum of this function, and vertices are connected by walking along the direction of least change of the distance transform to form edges. Another, which seems simpler and more robust, is to just grow a sphere from each tile until it intersects an obstacle tile; if it intersects two, it's an edge tile, and if it intersects more than two, it's a vertex (but with some experimenting, this latter approach only seems to work in the Euclidean metric).
I used the Manhattan metric. The way I did this was to exploit the information we've been propagating about who the nearest obstacle tile is; I did some experiments, and it works nicely. Here's how the method I used works: For each tile, consider the set of neighboring tiles {SELF, EAST, NORTH}. Then iterate over all 3 pairs of this set, computing distances between corresponding closest-obstacle-tiles. If the sum-of-squares of these distances exceeds a threshold, mark the tile as an "edge" tile. A "vertex" is then just any "edge" tile with more than two 4-connected neighbors who are also edges. This works quite well; I get the following results:
Just so I don't have to edit my post, I'm going to keep calling these vertices and edges "Voronoi" vertices and edges, though in reality the edges are "medial axes," and the graph is called the "shock graph."
Now, along each Voronoi edge (really: edge of shock graph), there is at least one tile whose distance-to-closest-obstacle value is minimal, and you can easily search along the edge to find it. I would call this value the "width" of that edge, and the tile at which it is found the "chokepoint" on that edge.
Once you have these numbers, you can forget about the underlying tile map. You just have a graph (which happens to be a Voronoi diagram, but that's no longer important), with values assigned to the edges. You can identify your base with one or more nodes of the graph (more on this later*), and your opponent's base with another set of nodes. Now what you're looking for, to achieve a defense, is a graph cut that separates you from your opponent. To select the cut, you'd assign a cost to each edge (e.g. a weighted sum of the "width" of the edge, and its distance from your base, though how to select these costs is itself an interesting question**), and then look for a minimum-cost graph cut (where the cost of the cut is the sum of the costs of the edges cut). Once you have this cut, you build a fortification at a chokepoint (as defined earlier) on each cut edge.
* About mapping your base's footprint to the Voronoi diagram: The Voronoi diagram implicitly defines a "deformation retract" of the environment. If you map your base's footprint through the deformation retract, you'll end up with a "footprint" on the nodes and edges of the Voronoi diagram. In less fancy language, when you first did your brushfire algorithm, you could have kept track of each tile's children; then, for any given tile, you can follow the chain of children until you end up on a Voronoi edge/vertex.
** One thing I haven't considered at all is that, sometimes , you might be willing to "stretch" your empire a little if doing so will allow you to control more resources. Then, you might penalize an edge less, even if it is wide, or a little too far from your base, if choosing to fortify it would keep e.g. a mineral patch within your cut of the graph. You can imagine flood-fill type algorithms that compute edge costs based both on the resources that the corresponding cuts contain, the widths of the edges, and the distance from your base.
#4 Members - Reputation: 122
Posted 06 May 2011 - 12:25 PM
I'm trying your suggestion but am having a problem with getting the vertices and edges. How should I be testing each tile, as right now I'm looping through them, testing each neighbour and if 3 have different obstacles its a vertex. But the result isn't what I would expect.
Is it because I've gone wrong with the first step? My obstacles are just tiles that are marked unwalkable then I propagate getting this result: http://i.imgur.com/q2Sm4.gif
Is it because I've gone wrong with the first step? My obstacles are just tiles that are marked unwalkable then I propagate getting this result: http://i.imgur.com/q2Sm4.gif
#5 Members - Reputation: 958
Posted 06 May 2011 - 03:43 PM
I'm trying your suggestion but am having a problem with getting the vertices and edges. How should I be testing each tile, as right now I'm looping through them, testing each neighbour and if 3 have different obstacles its a vertex. But the result isn't what I would expect.
Is it because I've gone wrong with the first step? My obstacles are just tiles that are marked unwalkable then I propagate getting this result: http://i.imgur.com/q2Sm4.gif
Oh, damn; I messed up my description of the Voronoi nodes and edges; give me a bit and I'll fix it...
#7 Members - Reputation: 122
Posted 07 May 2011 - 07:27 PM
Thanks for all the information, its been a great help. I'm attempting to implement your method and am nearly there but have a couple questions.
Generally whats best to be used for the threshold? As using a single value for all tiles gives the best results however it will cause narrow paths a few tiles wide to be skipped. Or should I ignore this and find it later by path finding between vertices?
Finally, I'm not sure what your mean by "with more than two 4-connected neighbors who are also edges".
Generally whats best to be used for the threshold? As using a single value for all tiles gives the best results however it will cause narrow paths a few tiles wide to be skipped. Or should I ignore this and find it later by path finding between vertices?
Finally, I'm not sure what your mean by "with more than two 4-connected neighbors who are also edges".
#8 Members - Reputation: 958
Posted 07 May 2011 - 08:06 PM
Generally whats best to be used for the threshold? As using a single value for all tiles gives the best results however it will cause narrow paths a few tiles wide to be skipped. Or should I ignore this and find it later by path finding between vertices?
I'm not sure. I was using a constant value of 20, but I figure that's the sort of thing you determine by tuning. To be honest, any time I see a threshold in an algorithm I get a feeling of "ugliness," but I'm not sure what a better way would be. There might be cleaner techniques in the literature. As you turn the value down, you start getting more paths that branch off towards small, "irrelevant" concave portions of the unwalkable set. (I figure you've played with it and know what I mean.)
It also seems to me that it might be nicer to use "length of shortest path through unwalkable set" instead of Manhattan/Euclidean distance here, but that's expensive and a little bit of a pain to implement, so I didn't bother.
Finally, I'm not sure what your mean by "with more than two 4-connected neighbors who are also edges".
Each tile has neighbors. The neighbors are defined in a 4-connected sense (north, south, east, west -- no diagonal (that's called "8-connected")). Tiles can be labeled as "edge" tiles. I'm talking here about any tile with the property that both (1) it's labeled an "edge" tile, and (2) more than two of its neighbors are labeled "edge tiles."
(It's the more-or-less obvious test that you'd come up with yourself for where two or more rasterized curves meet.)
Thanks for all the information, its been a great help.
Yeah, no problem. It gave me an excuse to look at the medial axis literature, which was interesting. Before you'd asked, I hadn't really "felt" why this was a slightly different / harder problem than the standard Voronoi one.
#9 Members - Reputation: 122
Posted 08 May 2011 - 03:05 PM
I'll probably have to combine some techniques and add some other steps as I think the complexity of the maps I'm trying to analyse are giving errors.
For reference here are some of the maps I'm trying to decompose: Gallery
First being to not propagate from small obstacles when calculating the distance to obstacle as it leads to edges in unexpected places.
Then I think I'll try to find a solution for the distance through the unwalkable set, as it will give the best results. Maybe grouping them up so that their group id can be first checked to see if they are even connected.
Then finally a step to merge the regions if the choke point between them is not noticeably smaller then the regions.
For reference here are some of the maps I'm trying to decompose: Gallery
First being to not propagate from small obstacles when calculating the distance to obstacle as it leads to edges in unexpected places.
Then I think I'll try to find a solution for the distance through the unwalkable set, as it will give the best results. Maybe grouping them up so that their group id can be first checked to see if they are even connected.
Then finally a step to merge the regions if the choke point between them is not noticeably smaller then the regions.
#10 Members - Reputation: 1257
Posted 09 May 2011 - 10:47 AM
If you already know the path (a chain of adjacent pixels/tiles, not a polygon) you can compute the distance from each step of the path to the closest wall cell (in other words, the size of the largest clear disc that is centered on that point of the path and doesn't overlap obstacle pixels). You might call this distance the path's "width".
The local minima of the path width are the choke points (some might be so wide that you don't want to treat them as such); if you want choke regions instead, take the union of all narrow enough portions of the path.
If you also need to compute good paths, you can preprocess the map with a morphological dilation by the shape of your moving objects, marking as obstacles all location where a part of the object would overlap a wall; you are then left with traditional pathfinding on a graph that includes the valid locations of agent centers.
If you want you can also tweak path cost values by making points with a smaller path width progressively worse (favoring the middle of wide passages, where path width is greater). If the weight of this distance transform component is very large compared to that of path length you approximate a medial axis, but the resulting wall-avoiding path can be unpleasantly longer than the wall-hugging shortest path: experiment with important example cases and with nonlinear distance terms (huge for small distances, to avoid walls that matter tactically, small but never zero for large distances to break ties the right way and produce nice path shapes).
The local minima of the path width are the choke points (some might be so wide that you don't want to treat them as such); if you want choke regions instead, take the union of all narrow enough portions of the path.
If you also need to compute good paths, you can preprocess the map with a morphological dilation by the shape of your moving objects, marking as obstacles all location where a part of the object would overlap a wall; you are then left with traditional pathfinding on a graph that includes the valid locations of agent centers.
If you want you can also tweak path cost values by making points with a smaller path width progressively worse (favoring the middle of wide passages, where path width is greater). If the weight of this distance transform component is very large compared to that of path length you approximate a medial axis, but the resulting wall-avoiding path can be unpleasantly longer than the wall-hugging shortest path: experiment with important example cases and with nonlinear distance terms (huge for small distances, to avoid walls that matter tactically, small but never zero for large distances to break ties the right way and produce nice path shapes).
Produci, consuma, crepa
#12 Members - Reputation: 122
Posted 18 May 2011 - 12:16 AM
Thanks again for all the help, I couldn't get the results that I wanted with the method you posted but it helped me come to a solution that's giving some nice results and is pretty fast. Thought it would be a good idea to post the results and algorithm.
For the algorithm:
Step 1: Flood fill from the tiles to their neightbours that have the same walk-ability as it, assigning a shared value, such that comparing the value of 2 tiles will tell whether they are connected. Also count the number of tiles for each connected unwalkable set and if the total is low, I used 172, designate that "region" a small obstacle.
Step 2: Same as your first step, calculate the 8-connected tiles. Though having a cost of 14 when it moves diagonally and 10 otherwise. It also doesn't assign an initial value to those tiles marked as small obstacles in the previous step.
Step 3: Then in a loop, continue until there are no unvisited tiles remaining:
Find the tile with the largest clearance(distance to obstacle) that hasn't been visited yet. Propagate from it tile to it's neighbours in the same way as step 2, though only travel to the 4-connected tiles, using a Brushfire Algorithm to travel through the tiles with a larger clearance first, skipping those already marked as chokepoints. While traveling, store the last tile that had the lowest clearance along the current path.
At each step compare the clearance of the start tile, the clearance of the current tile and the clearance of the lowest clearance tile so far. If certain conditions are met the lowest clearance tile will be marked as a choke point. The check I have so far is if the lowest value is less that 85% of the start tile or 75% of the current tile, then it is a chokepoint. The tiles between the obstacles that form the chokepoint are then marked off in a straight line, and all tiles on the other side of the chokepoint are removed from the current brushfire search. Then the burshfire algorithm continues until it cannot spread to any more tiles due to unwalkable tiles or chokepoint tiles.
The loop then continues, giving you after each step all the tiles that form this Region, the "center" of this region(the original tile) and the chokepoints connected to this region.
I still need to tweak the choke point detection values, but here are the results so far:
http://laccolith.imgur.com/results
For the algorithm:
Step 1: Flood fill from the tiles to their neightbours that have the same walk-ability as it, assigning a shared value, such that comparing the value of 2 tiles will tell whether they are connected. Also count the number of tiles for each connected unwalkable set and if the total is low, I used 172, designate that "region" a small obstacle.
Step 2: Same as your first step, calculate the 8-connected tiles. Though having a cost of 14 when it moves diagonally and 10 otherwise. It also doesn't assign an initial value to those tiles marked as small obstacles in the previous step.
Step 3: Then in a loop, continue until there are no unvisited tiles remaining:
Find the tile with the largest clearance(distance to obstacle) that hasn't been visited yet. Propagate from it tile to it's neighbours in the same way as step 2, though only travel to the 4-connected tiles, using a Brushfire Algorithm to travel through the tiles with a larger clearance first, skipping those already marked as chokepoints. While traveling, store the last tile that had the lowest clearance along the current path.
At each step compare the clearance of the start tile, the clearance of the current tile and the clearance of the lowest clearance tile so far. If certain conditions are met the lowest clearance tile will be marked as a choke point. The check I have so far is if the lowest value is less that 85% of the start tile or 75% of the current tile, then it is a chokepoint. The tiles between the obstacles that form the chokepoint are then marked off in a straight line, and all tiles on the other side of the chokepoint are removed from the current brushfire search. Then the burshfire algorithm continues until it cannot spread to any more tiles due to unwalkable tiles or chokepoint tiles.
The loop then continues, giving you after each step all the tiles that form this Region, the "center" of this region(the original tile) and the chokepoints connected to this region.
I still need to tweak the choke point detection values, but here are the results so far:
http://laccolith.imgur.com/results
