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).

  • 3
    Why do you need to make it a unit square? An abstract graph is already well-suited for path-finding algorithms2012-03-02
  • 0
    Well, I guess what I'm trying to get at is that it seems to me that ALL pathfinding solutions can be embedded by using the unit square. It's my understanding that if used a more classical approach such as A* that I have to calculate a new path each time. I know it's efficient. But if I go with this route, can't I simply calculate the route directly? I'm not guaranteeing it's shortest, but to me the idea seems intriguing.2012-03-02
  • 5
    When you start with "I don't know topology" and end with "Assume genus zero." it comes across as "I heard about this mathematical tool which sounds totally awesome and could solve my problem", however usually when you hear about these mathematical tools that solve your problem they are abstract, very abstract, and the implementation of them to your problem is actually something completely different (e.g. you end up with graph theoretical problems instead), and even then it only vaguely looks like what you originally intended.2012-03-02
  • 0
    I do have some background in graph theory from when I studied math for my degree. However, I really don't have any more background in topology than hearing another student give a talk on it once, hence the "Assume genus zero". So guilty as charged - but don't hesitate to use abstract graph theory answers. In fact, I'd probably get them better. The problem is that while I took some graph theory, I don't know topology and thus don't know common representations of spaces as graphs (which is what you seem to be implying topologists use). If you point me to scary abstract answers, I'm good. Thanks!2012-03-03
  • 0
    What? Me? I don't know how to solve that. I also don't really know if it's true to say that topologists represent spaces as graphs. You can stretch and say that simplicial stuff is a bit like a graph, but that would be missing the point. I just tried to give an example and used graph theory as a generic example.2012-03-03
  • 0
    You might want to retag this "differential-geometry", since I think you're looking for a diffeomorphism, not just a homeomorphism. (I can't comment yet. Feel free to convert this to a comment.)2012-03-03
  • 0
    @Mike: the example in the question does not look like a diffeomorphism.2012-03-03

1 Answers 1