Shortest path problem.
I have this map, built up from irregular polygones. Every polygone has different terrain and "movementcost" and some polygones are not possible to enter.
I would now like to be able to find out the shortest path between two pixels on the map.
I want to use the A-star algorithm, and this would be rather simple if I had the map divided into dots, where I would know the distance and terrain between all dots.
But here if I divide the map up into dots it would mean all the pixels that go around all the sides of the polygones (I guess). This would mean a very large amount of dots.
Is there another way of doing this?
Im sorry if I'm unclear in my description, a little hard to explain without an image.
Assuming each step in the algorithm is from one polygon to another, each 'enter-able' polygon can be represented as dot in the graph.
But you want the distance between pixels. That implies that steps are not from one polygon to another. Can you clarify?Also, how many polygons are we talking about?
This is a rather complex issue. I heard a lecture from a german guy who not too many years ago had a good algorithm for this.
You CANNOT simply view all polygons as a a node in a graph, since you can enter a polygon at any side, at any point, and exit any side at any other point, in your path. The distance travelled on the polygon times the movementcost of the polygon is the cost for taking this route. Hence every polygon can be travelled in indefinitely many ways. So you need to solve the problem approximately.
The idea of the algorithm was as follows:
Let every corner of the polygon be a vertex (node).
Divide every side into as many parts as you want - the more parts, the more precise algorithm. Every dividing point will also be a vertex.
From every vertex you can travel to any other vertex on the other sides of the polygons that this vertex is part of, or alongside the side of the polygon. The distance or weight of this edge is weight = distance*movementcost. (distance I hope you can figure out how to calculate). You don't need to store the edges of the graph, the edges can be determined during runtime in this manner.
Do the simple Dijsktra algorithm on this.
Gil
Interesting.
Do you want to find the very shortest path, or do you want to find a quite short path fast?
In theory the problem might be solved exactly. Yes, any polygon can be crossed in an indefinitely number of ways, but (assuming all polygons are convex) any crossing would be a straight line from one of the edges of a polygon to another edge. The movement cost of such a crossing might be expressed not as a number, but as an equation containing two variables indicating at what point of the two involved edges the route starts. This crossing may be minimized by changing the value of the two variables (using mathematical derivation). But you can not minimize each crossing locally, because the exit point of one polygon is the entry point of another. So you have to create one huge equation for the entire route, and you have to find the minimum of this equation, and you have to that for each possible route.
This would give you the exact answer (after your pc has run on 100 percent cpu for a few weeks...)
In practice I think simulated annealing (or even a genetic algorithm) could be the way to go(?)
Hello!
Thanks for the replies. I'll clearify myself a bit.
The map is devided into irregular polygones. Could be several hundered. Every polygone with its own terrain, some impossible to pass. I want to be able to calculate the shortest route between one pixel in or on a polygone border.
I guess this can be done through Dijsktra or Astar, with the first step beeing the distance from the starting pixel to the surrounding polygone's edges'es pixels. And then onto all the other neighbouring polygones edges'es pixels, and so on, untill the last distance is the goal pixels polygones edges'es pixels to the goal pixel.
All these distances should be modified by its momentcost.
This would mean possibly many thousands of dots(pixels), and would just be to much I guess, because I really dont need to be very exact.
So probably the only way is to take every maby 20 pixels on the edges of all polygones. Like gilroitto says, if I understood him right. I didn't really get what you meant Ragnvald_id2.
Well thanks again for the help.
Could anyone comment on if they think it would add much complexity if not all polygones are convex. It could be much work to calculate every lines terrain. Every lines every pixel would have to be tested for in what polygone it is and calculated for what momentcost it should have.
Another approximate approach is to embed your polygons in a graph (each vertex of each polygon
becomes a vertex in the graph). Then find a sort of inverse of the graph whereby the centre of each polygon
becomes a vertex in the new graph. The edges in the new graph correspond to the movement cost between
the centres of adjacent polygons. The movement cost is Ma*Da+Mb*Db where Mx is the Movement cost of
polygon x and Dx is the distnace travelled inside polygon x.
Edges that have a vertex in a non-enterable polygon can be removed to reduce the siez of the graph.
Then standard shortest path algorthms can be used. The path however will allways be through the
center point of each polygon on the route.
matfud
Thanks for the reply matfudIt should be possible to set a starting point and end point anyware in any of the polygones.
You got me right JungleSore.
> Could anyone comment on if they think it would add much complexity if not all polygones are convex.
> It could be much work to calculate every lines terrain. Every lines every pixel would have to be tested
> for in what polygone it is and calculated for what momentcost it should have.
If a polygon is not convex, divide it until all parts are convex.
The cost for calculating the lines terrain should not be costly: For crossing a surface you have one movementcost, going alongside a line just choose the cheapest movementcost. For calculating weight of edge: movementcost * length. And length is simple multiplications and squareroots. The cost will be the priority queue for Dijkstra and the memory needed for handling all vertices. Be sure do have a good priority queue, such as a good heap.
> So probably the only way is to take every maby 20 pixels on the edges of all polygones.
If you can avoid thinking in "pixels" I think it's easier and you'll have more exact calculations. If you have the positions of the corners, then calculate the intermediate vertices in floating (double/float) positions.
> Another approximate approach is to embed your polygons in a graph (each vertex of each polygon
> becomes a vertex in the graph). Then find a sort of inverse of the graph whereby the centre of each polygon
> becomes a vertex in the new graph. The edges in the new graph correspond to the movement cost between
> the centres of adjacent polygons. The movement cost is Ma*Da+Mb*Db where Mx is the Movement cost of
> polygon x and Dx is the distnace travelled inside polygon x.
This algorithm has a flaw: Very often it will be much more efficient to move alongside vertices. But it may be a very quick solution for fast approximation algorithm, and the route will be modified in the end by straightening all turns through the center of the polygons.
If 2 polygons are attached to each other only by the corner, and not a side, the "thought" travell way and the calcuated cost therafter, should be by it's corner, not crossing any other polygons, even if it means that edge will be bent.
Gil
>It should be possible to set a starting point and end point anyware in any of the polygones.
It a crude approximation. If you need to start at any point in a polygon first find the nearest polygon
center and move there. The last move you make will be from the last polygon centre to the position
in you destination polygon.
>This algorithm has a flaw: Very often it will be much more efficient to move alongside vertices. But it may
>be a very quick solution for fast approximation algorithm, and the route will be modified in the end by
>straightening all turns through the center of the polygons.
Yep. You are correct. It should however be fast to compute an approximate route using this approach.
Whether it is of any use depends on the purpose for which JungleScore wishes to use it. If it is being
used for a game then this will probably be accurate enough.
If you need more accuracy you can add extra nodes into the graph. A vertex at the point where the line
between adjacent polygon centers crosses the boundary between them for instance. If you also keep the
original polygon edges in the graph then you can tranverse along those edges also.
This would slow things down quite a bit though as the shorest path algorithm runs in O(|E|log|V|)
(E=edges, V = vertices) and then only if implemented on a heap.
matfud
another way of improving the accuracy is to subdivide your polygons. You will probably need to do this
for non-convex polygons anyway. Finding the set of 3 sided polygons that constitutes your arbitraty
polygon may be a good idea. (its easy to find the centre of a 3 poly)
matfud
Thanks again for the replies.
The program is meant to be able to calculate the (theoritical) shortest distance between two points on a map. Could be used for a game, but would probably be overkill like you say matfud, maby more for orienteering (or something). But right now Im just interested in the problem.
The terrain polygones could be rather big and cover a large percentage of the map so this could mean a big margin of error if only the centers are beeing used I guess.
Would subdividing the polygones have any performance boost, or only in accuracy? There would be a smaller number of "pixels" to test at a time if using the method you suggested gilroitto.
> Would subdividing the polygones have any performance boost, or only in accuracy?
The algorithm will take longer time to compute with more polygones of course. Only reason for this as I see it is if you have polygons that aren't convex, since creating an algorithm for non convex polygones will be unnecessary complicated. For the first algorithm described by me, there will be no improvement in accuracy if sub divinding polygones, but accuracy will be improved in matfuds algorithm suggestion.
Gil
> Thanks again for the replies.
> The program is meant to be able to calculate the
> (theoritical) shortest distance between two points on
> a map. Could be used for a game, but would probably be
> overkill like you say matfud, maby more for
> orienteering (or something). But right now Im just
> interested in the problem.
I think you means fastest route. The shortest is a stright line between the start and end points (on flat
surfaces). Haveing "no-go" regions makes it a bit more complex then this. Finding the fastest route is
actually a very complicated problem (computationally). Also there may be more then one route of
equivelent speed.
A perfect solution to this algorithm would take an awfully long time for your computer to solve it. Gil's solution
is an approximation to the fastest route (you can change the accuracy by changing the number of
subdivisions you use on each polygon edge). Mine is a faster and less accurate approximation to the fastest route (which also can have its accuray changed. In this case by subdividing the polygons).
Another option is to combine the approaches. Use my algorithm first to find a rough corridor of polygons
that are likely to be included in the route. prune ploygons from the graph that are not near this path
then use a more accurate approach such as Gils to find the path within that corridor.
you will have to look into the maths and experiment to find the tradeoff point that is most suitable for
you. I don't know how exactly how each of the algorithms scale but here are some thoughts.
My approach creates a vertex for each polygon. if the number of polygons is N then V=N. Assuming 3
sided polys you can have at most N-1 adjacent polygons. Although this would be very rare. Look at
your map and find the average number of neighbours a polygon has this value is E. use the O(|E|log|V|) to
find the expected complexity of the algorithm.
Gils algorithm is also based on Dijsktra's shortest path algorithm. however the number of potential
paths through a ploygon (Edges in the graph) is proportional to (P^3)/2 if each edge of a ploygon is
subdivided with P nodes. The number of nodes in the graph is V=3*N*P. (Assuming 3 polys again).
And E=V(P^3)/2
You better check that though as I'm not sure if I have understood Gil correctly.
> Would subdividing the polygones have any performance
> boost, or only in accuracy? There would be a smaller
> number of "pixels" to test at a time if using the
> method you suggested gilroitto.
Subdividing the polygons would make both algorithms slower. Doing so would not necessarilly increase the
accuracy of Gils method. It would increase the accuracy of mine. Note that you do not have to subdivide all
polygons. Only those that are above a certain size. Your subdivision algorithm would keep subdividing
polygons until they are below a specified size.
matfud
> Subdividing the polygons would make both algorithms
> slower. Doing so would not necessarilly increase the
> accuracy of Gils method. It would increase the
> accuracy of mine. Note that you do not have to
> subdivide all
> polygons. Only those that are above a certain size.
> Your subdivision algorithm would keep subdividing
> polygons until they are below a specified size.
Just brainstorming here but what if you did what I suggested in my first response (which I made based on a misunderstanding of the problem) once and determine the top x solutions. Remove all nodes except the nodes that are used in these top solutions. Subdivide the polygons and repeat until you get to the an acceptable level of precision.
Just an idea:
I remember that light actually does travel along such a path as you describe when it goes through material with different optical density (i.e. differen speeds of light). So you might be able to use algorithms from raytracing?!
One comment on matfud's algorithm: I am not sure if it automatically becomes more precise when the number of polygons increases, since the old path (with fewer polygons) is not (necessarily) a solution for the problem with more polygons. So if you split the polygons the wrong way, you might end up with a weird zick-zack-path that is actually longer.
regards
Spieler
Well what a great responce! You helped me alot.
If I summarize what I understood beeing two different approaches; there is the more accurate but slower proposal with letting every 20th edge coordinate be a dot, and splitting concave polygones up into smaller polygones (into triangles) which gilroitto mentioned.
And then theres the one matfud mentioned a faster not so accurate way. Dividing the polygones into small enough polygones (also triangles?) and letting the centers be the dots that matfud mentioned.
Hope I got this right.. Maby you could even get me a tip on how the polygones could be divided into triangles? Well anyway, thanks alot for the help!
for each polygon: start at on corner;
take the next two cornors. These two are your first triangle.
continue with the remaining polygon (which has the same corners as the old one minus the second corner)
until your remaining polygon has only two corners, which means it isn't a real polygon anymore
regards
Spieler
1 Cut all concave polygons into convex parts.
2 Create a random route (route A): Cross the starting polygon from the starting point to a random point on one of its edges. Cross the next polygon from the entry point to a random point on one of its edges. Repeat until you reach the polygon of the destination, where you simply cross from the entry point to the destination point.
3 Create a new route (route B) that is a copy of rout A with some random modifications made to it.
4 Set A to be the shorter of the two routes A and B.
5 Go to step 3 or stop.
When to stop: When A has been shorter than B in step 4 for a significant number of consecutive times (or after a specific number of iterations).
The first times you pass step 3, you let the random modifications be very significant. Then, as the iterations go on, you gradually reduce the modifications done in step 3, allowing only small changes (assuming you have found a good route, and just need to do minor optimisations on it).
Ragnvald
Thanks Ragnvald_id2 and spieler
Ragnvald_id2: this what you describe would give the most exact way of getting the distance, and would be the way I mention above as the first and more exact way. You only have to choose how exact you want to be and choose how many steps you want between every dot on every edge. Just as an example I mentioned 20 above. It could be 0.001 as I see it but that would mean an enormously long calculation. If I got you right.
Spieler: With an irregular concave polygone this could mean that one line crosses another concave corner. For example an polygone formed as an X would mean some problems I think.
> Ragnvald_id2: this what you describe would give the most exact way of getting the distance, and would
> be the way I mention above as the first and more exact way. You only have to choose how exact you want
> to be and choose how many steps you want between every dot on every edge. Just as an example I
> mentioned 20 above. It could be 0.001 as I see it but that would mean an enormously long calculation. If
> I got you right.
This approach can produce very accuracte results but then so can the other one suggested here. It also
has its flaws. If you just randomly move parts of the path then it will take forever (literaly) to converge on
the optimum path. If you use some form of directed serach to speed up the serach then you end up with
the limitations of the search method. The technique is similar to that of "snakes" from image processing.
They can produce very good results but are also prone to getting stuck in inappropriate routes. It is
another viable approach to add to your growing collection though.
matfud
> Ragnvald_id2: this what you describe would give the most exact way of getting the distance, and would
> be the way I mention above as the first and more exact way. You only have to choose how exact you want
> to be and choose how many steps you want between every dot on every edge. Just as an example I
> mentioned 20 above. It could be 0.001 as I see it but that would mean an enormously long calculation. If
> I got you right.
This approach is mainly used for problems with hopeless complexity, such as TSP. Random algorithms has major problems:
* You test it on some testcases, and adjust parameters so they give results on these cases. But then some unexpected case comes up and your random algorithm performs very badly. One critical parameter for the random algorithm described above, is how big changes should the random changes be.
* You will never find narrow winding paths between areas with high movement cost. Eg, you have mountains, but a valley winding between them that is very quick. Most random changes will go over some very costly mountain and give very very bad results and be disregarded.
* You are prone to get stuck in inappropriate routes (as matfud said).
Gil
Well thanks all of you, I certanly got some ideas!
> Spieler: With an irregular concave polygone this could
> mean that one line crosses another concave corner. For
> example an polygone formed as an X would mean some
> problems I think.
you are right ... you can't work on an arbitrary corner ... **** ... not even working on a convex corner does work ... I'm stuck
this shall do it http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.html
Sombody suggested turning each polygon into a node.
But what if you turned each vertex into a node and each line segment into an edge. The weight of each edge is the minimum of the two adjacent polygons. Given you starting location is inside a polygon, pick the closest vertex. Run Dijkstra's algorithm.
At this point you can look for short cuts in the path that cross a polygon straight instead of traveling along the edges of the polygon.
Nice article. Now, let me defend my idea:
This approach is mainly used for problems with hopeless complexity, such as TSP.
I believe the problem described is of "hopeless complexity".
The approach is called simulated annealing, and the Travelling Salesman Problem is often used as a text book example on how to apply the algorithm.
You test it on some testcases, and adjust parameters so they give results on these cases. But then some unexpected case comes up and your random algorithm performs very badly.
True, but unfortunately that is the case for non random algorithms as well.
One critical parameter for the random algorithm described above, is how big changes should the random changes be.
The changes should be very big during the first iterations, and then gradually diminishing.
You will never find narrow winding paths between areas with high movement cost. Eg, you have mountains, but a valley winding between them that is very quick. Most random changes will go over some very costly mountain and give very very bad results and be disregarded.
Important point! But it depends on your implementation. A proper implementation of the random choosing of the next polygon crossing should probably not have a greater chance of hitting a wide edge than a narrow:
You are at a point and have a number (for example 2) of possible edges you can move to. You could make a random (50-50) choice. Or you could make a random (70-30) choice... You could adjust the probability of hitting an edge according to the movement cost of the polygon on the other side of that edge, according to the width of the edge, according to the distance from that edge to the destination... There are many possibilities here! Once you have chosen an edge, you have to chose a (random) point on that edge. And again you can play with the probabilities. You could for example increase the probability of hitting the edge as closer to your origin if the polygon you are moving on has a high movement cost.
You are prone to get stuck in inappropriate routes (as matfud said).
The whole idea is to make big random changes in the first iterations, and thereby find a quite good route (that you probably will be stuck with), then you do smaller changes and effectively optimize the root you have chosen.
> This approach is mainly used for problems with
> hopeless complexity, such as TSP.
>
> I believe the problem described is of "hopeless
> complexity".
> The approach is called simulated annealing, and the
> Travelling Salesman Problem is often used as a text
> book example on how to apply the algorithm.
No, Dijkstra is not hopeless at all in complexity, it's n log(n) which almost no algorithms beats. It's just many nodes.
>
> You test it on some testcases, and adjust
> parameters so they give results on these cases. But
> then some unexpected case comes up and your random
> algorithm performs very badly.
>
> True, but unfortunately that is the case for non
> random algorithms as well.
No, since Dijkstra garantuee to give you the best result, and using this in a slightly approximative way only gives you slightly worse results than the absolute best. So then it doesn't matter what instance you have.
>
> One critical parameter for the random algorithm
> described above, is how big changes should the random
> changes be.
>
> The changes should be very big during the first
> iterations, and then gradually diminishing.
And you have no clue whether you "should" continue to do large changes since the best paths can only be found by big changes.
>
> You will never find narrow winding paths between
> areas with high movement cost. Eg, you have mountains,
> but a valley winding between them that is very quick.
> Most random changes will go over some very costly
> mountain and give very very bad results and be
> disregarded.
>
> Important point! But it depends on your
> implementation. A proper implementation of the random
> choosing of the next polygon crossing should probably
> not have a greater chance of hitting a wide edge than
> a narrow:
> You are at a point and have a number (for example 2)
> of possible edges you can move to. You could make a
> random (50-50) choice. Or you could make a random
> (70-30) choice... You could adjust the probability of
> hitting an edge according to the movement cost of the
> polygon on the other side of that edge, according to
> the width of the edge, according to the distance from
> that edge to the destination... There are many
> possibilities here! Once you have chosen an edge, you
> have to chose a (random) point on that edge. And again
> you can play with the probabilities. You could for
> example increase the probability of hitting the edge
> as closer to your origin if the polygon you are moving
> on has a high movement cost.
Yes, you can do smarter ways of choosing random paths.
>
> You are prone to get stuck in inappropriate routes
> (as matfud said).
>
> The whole idea is to make big random changes in the
> first iterations, and thereby find a quite good route
> (that you probably will be stuck with), then you do
> smaller changes and effectively optimize the root you
> have chosen.
>
Regardless my critisism, your approach IS plausible. Especially if you cannot afford the memory used by Dijkstra. However me personally I would choose matfuds approach any time above a random approach if my approach seems to give too many nodes. Random approaches are just too messy and too uncertain for my taste.
Gil
I red your criticism and reread your first post, Gil. I am convinced. Dijkstra isnt that bad after all...
I guess you even could find the perfect solution (in most cases) by first finding a path using your Dijkstra approach, and then use a different approach to optimize the route by adjusting the points where you cross the edges along the edges you cross.
JungleSore,
If you you are trying to find a solution for this problem in game context - ask yourself a question: do you really need to work with pixels? Will the moving objects have a size of a single pixel? Most likely - no. If the size of the object is 10s of pixels - that you can divide your map into a set of larger areas (create a GRID). Each cell in the grid does not have to be rectangle - it could be a polygon with 6 or 8 (or even more) angles...
This way you can apply the same path finding algorithms but the load on the CPU will decrease by a large factor.
And with the grid, if the path comes into a polygon, you can set up anoter (thinner) gridif you want more precision...
> this shall do it> http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.htmlLOL. I'm in my final year at www.info.ucl.ac.be.Le monde est petit.
