Maps Pathfinding Nodes

Apprentice
Posts: 14
Joined: 2007.04
Post: #1
Hello, this is not necessarily for a game but I thought I could easily find an answer here. I want to develop a virtual map for my city, the choice is to use nodes in intersections with paths to north south east and west to represent single and double directions roads. But I have a big doubt, if the city didn't have tunnels and bridges and elevated roads it would be easier as it would be just a 2D grid but it has. How do I represent those elements?
Quote this message in a reply
Moderator
Posts: 452
Joined: 2008.04
Post: #2
You're on a good track for making nodes for intersections, but don't constrain yourself to 2D. When you create a graph (edges and nodes), you don't need to constrain yourself to a single dimension. Bridges and tunnels are just more edges in your graph.

I'm assuming you're planning to use the graph of your city for pathfinding, but on a second read, maybe that's not the case?
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #3
Yeah, I'm going to do that but actually is just an exercise. I'm not doing it for any commercial purpose but it could turn into something like that, who knows. Thanks for the answer, it clear my doubts.
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #4
When you want to do pathfinding, you'd probably go for an A-star algorithm (which is a dijkstra algorithm, basically). You can then represent bridges, tunnels, mountains or any other obstacles with weighted edges, which means your edges have a number, its weight, associated with them.

A star handles weighted edges (as long as this weight is > 0) well, so it makes no real difference or complication if you want to have bridges, etc., except that you need to store the weight in your edge struct/class.
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #5
What do you mean with weighted edges? Like the cost of using the edge?
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #6
In the case of a pathfinding map, the weight would be the distance you traveled.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #7
I was thinking exactly that, but I thought it was called "cost" or something similar.

I was thinking about using some sort of array to store a pointer to each node/object so I can access them for special purposes without using the edges (like changing the cost/weight on the fly), is that a good idea or should I just leave them self-linked and access them through the edges?.
Quote this message in a reply
Member
Posts: 567
Joined: 2004.07
Post: #8
Hmm, I created a nifty ray-casting technique that looked for edges of objects and then determined the best route—for 3d games, I found that this was the best approach; you're not constrained to grids.

It's not magic, it's Ruby.
Quote this message in a reply
Member
Posts: 59
Joined: 2007.12
Post: #9
jigzat: Not sure what you mean. Generally, you have a simple array of nodes. Every node then has a list of edges. These edges can have a cost/weight associated with them which you can change "on the fly" if you want so. You can access the edges via the nodes.

The cost would be higher for bridges, for example, because they can't be traversed as easy as an open field, for example.
Quote this message in a reply
Moderator
Posts: 452
Joined: 2008.04
Post: #10
I got the impression from the first post that each node you created had 4 links (one for each cardinal direction) connecting to adjacent nodes. That would explain why you'd have trouble with bridges. Like _ibd_ said, just maintain a list of edges for every node. You don't need to tie them to specific directions (like this node is connected to the north).

I think most people in this thread are assuming you're just creating a standard graph:

http://en.wikipedia.org/wiki/Graph_(mathematics)
Quote this message in a reply
Apprentice
Posts: 14
Joined: 2007.04
Post: #11
Yeah you are right, every node has 4 pointers that may or may not lead to a different node (depending of the street or avenue that represents, it doesn't necessarily means it is linked to a cardinal direction is just to represent double way roads) so I think I am basically doing a Graph. I talked about an array because in my university classes we worked with linked lists and we basically had a main pointer that pointed to a node which leads to NULL to the back and to other node to the front (if is not circular). We never stored the objects/nodes in any array, but I think it could be better if I store them on it and keep a directory of nodes.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  pathfinding for skating game in VC tenpenny 1 4,263 Sep 2, 2011 09:31 PM
Last Post: PoseMotion
  pathfinding, special case... blazer 8 4,795 Sep 27, 2005 12:40 PM
Last Post: GoodDoug
  pathfinding crashes Iceman 5 4,253 Jul 28, 2005 05:48 PM
Last Post: unknown
  Pathfinding stevejohnson 6 3,643 Oct 28, 2004 01:20 PM
Last Post: igame3d
  Pathfinding? Blake 3 3,152 Jan 13, 2004 09:34 PM
Last Post: Blake