5
$\begingroup$

First, I'd like to qualify this by saying I have no topology experience. So bear with me.

I've been contemplating pathfinding algorithms for a game I'm working on. I thought about the idea of trying to abstract the map into some notion of a topological space. I was wondering if there exists a way to arbitrarily do something like the following.

enter image description here

Ignoring issues like holes in the topological space, is there a way to generally transform something like the top image into something like the bottom one? If so, then it looks like I can more or less draw a straight line to find my path and then map the lines coordinates back into the first space to get my path. Embedding something like this could be done at compile time and thus seems like it could be tremendously powerful for running quick pathfinding!

To be precise, my exact question would probably be: is there an algorithm to translate a computer friendly version of a map (could be some form of a graph, or polygons) into a unit square that preserves the topology in this way? Assume genus zero (that is far as my buzzword knowledge goes).

  • 0
    @Mike: the example in the question does not look like a di$f$feomorphism.2012-03-03

1 Answers 1

1

The basic problem with your approach is that you want to replace something discrete (a graph) which is very well understood and suited to computer processing, with a continuous structure, and continuous things are notorious for entailing all kinds of new problems with rounding errors, finiteness of representation and so forth, when we attempt to do things with them on computers.

That is not progress.

More concretely, suppose you have an embedding of your map into the unit square (which is always possible somehow, if and only if the graph is planar), and compile some representation of that embedding into your program. Then, if you have a straight line between two points in the unit square, how are you going to find out algorithmically which rooms in the map are touched by your red line, and in which order? Your precise options depend on how you choose to represent the embedding, but in the cases I can readily imagine, you would end up doing either something equivalent to a graph traversals, or something more expensive than that, before your imagined red line can become an actual list of moves.

Also, you'll probably not end up with a shortest path when there are multiple possible ones. And if the length of the path doesn't matter to you, you can just arbitrarily declare one of your rooms to be a "hub" and then statically compute for each room which direction will take you closer to the hub. Then construct your path from A to B as the canonical A-to-hub path followed by the reverse of the canonical B-to-hub path.

  • 0
    Thanks for taking the time to answer, I appreciate the criticisms of the approach. The floating point issue is indeed a real one as is the shortest path and I have contemplated them both. However, I do not want to neglect the possibilit$y$ that there is some $f$orm of an integer based mapping that does not suffer from these issues. I cannot accept what you have listed here as an answer because you are working with supposition ("in the cases I can readily imagine", etc.). However, I really do appreciate you pointing these things out and I'll be thinking about them tonight.2012-03-04