Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Following on from my question about moving a sprite in a circle, assuming that you have a maze which is shaped like a a set of circles with holes in them and barriers between them.

Location of a sprite is stored in polar coordinates and then translated into cartesian coordinates to be rendered.

I'm going to assume that most path finding algorithms rely on cartesian geometry, is there a path finding algorithm I can use to allow "beasties" to chase my players sprite?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Actually, "most pathfinding algorithms" don't rely on any specific set of coordinate systems at all.

Most algorithms, like the most widely spread and probably most popular of them, the A* algorithm, just rely on a set of connected nodes in a graph and functions which estimate or straight up calculate the cost of moving from one node to another.

The awesome thing about this is that they work anywhere, in any kind of space or structure that you can imagine, as long as you have a way of calculating the cost of moving from one node to another.

As an answer to your question: You can (for example) use A* and construct your circle-y maze as a graph where the nodes are simply points on the imaginary circles that run through your maze, and the heuristic functions can still be based on the distance between two nodes.

If you wonder what your graph inside a circular maze should look like (wink wink :P), here's how I would basically do it (the black dots being the nodes and the lines being the connections between them):

enter image description here

I think my graph even has too many points, since you only need so much that your entities don't run into walls when they try to go straight from one node to another.

The better way to do this would be to use navigation meshes, meaning "surfaces as nodes" instead of just points (in this case a lot faster, since you'd need very few of them) would ). But if you understand how A* generally works they're not hard to implement at all.

share|improve this answer
    
Would you have to simplify your space so that each node was certain distance moved in that direction? away or would A* work for pixel by pixel movement? –  Omar Kooheji Aug 10 '11 at 18:19
    
Basically how do you define the granularity of what a node is. I know A* would work in a hexagonal/square tile based system, but how does it map to a non tiled game world? or is that another question? –  Omar Kooheji Aug 10 '11 at 18:20
    
I think you need to look for some more A* tutorials that explain how the algorithm works. It doesn't matter how the nodes are structured, it doesn't matter how far they're apart, if one of the nodes is in 2D space the next in 3D space etc. The granularity depends on your game: They shouldn't be so big that they overlap each other. Usually the nodes are just points, although if you need more freedom of movement for your characters, the nodes would be triangles in a navigation mesh. If you want to know more about that stuff, you need to do some research and ask new question if problems arise. –  TravisG Aug 10 '11 at 18:58
    
I've never implemented A* search but I have done a bit of reading on it. Given a Maze would you just assign nodes to areas on the maze and create a graph of those nodes? –  Omar Kooheji Aug 11 '11 at 9:12
    
Well, yes. I've edited in a picture and a little text to show you how my graph would look. Well, how my graph with certain constraints would look. –  TravisG Aug 11 '11 at 11:41

The exact geometry doesn't matter for path-finding algorithms. All that matters are connections between nodes. Applying any traditionally-Cartesian path-finding algorithm to your polar coordinates should be seamless--the algorithm doesn't care whether x and y are actually angle and distance.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.