1
\$\begingroup\$

I am working on A* pathfinding in Unity, using C#. I am implementing Dijkstra's shortest path algorithm. I have a Dictionary with nodes as keys and corresponding lists of adjacent neighbors as values, which I use for A*.

My pathfinding graph is a 2D grid of nodes, with 4 connected edges each. I want to give edges representing unobstructed paths a cost of 1, and increase it for obstacles.

Where should I store each edge's weight?


Currently I'm representing my grid of nodes as plain gameobjects in a 2D array. I thought of storing the weights in a dictionary with node-pairs as keys and weights as values. Would that work, and be efficient enough?

\$\endgroup\$
5
\$\begingroup\$

Various graph representations exist. Yours is an adjacency list with explicit vertices and implicit edges: Each vertex stores its adjacent vertices, each of which implies a directed edge to it.

vertices with implicit edges

In the above,
blue squares are vertex objects, arrows are references
vertex A's list of vertices is [ B ]
vertex B's list of vertices is [ A, C ]
vertex C's list of vertices is [ A ]

Only explicit objects can store data, hence why your graph structure can only store data on vertices, not on edges. To store data on edges, you'll need a graph data-structure with explicit edges also.

A simple way to do this is simply converting each vertex's list of other vertices into a list of edge objects. Each edge object can then store any arbitrary data (for example, its weight), along with its destination vertex.

vertices with explicit edges

In the above,
blue squares are vertex objects, red circles are edge objects, arrows are references
vertex A's list of outgoing edges is [ E2 ]
vertex B's list of outgoing edges is [ E1, E4 ]
vertex C's list of outgoing edges is [ E3 ]


In C#, you can implement this (in very abstract terms) by creating a class Edge { Node destination; float weight }, to go with your class Node { Edge[] outgoingEdges; } and add what other properties you need.


Your implementation idea would work too. Using further dictionaries instead of objects avoids having to write an edge class. The new dictionary is effectively a little database of little edge objects.

However, there are some downsides: If your graph changes (some nodes or edges disappear), dictionary entries aren't automatically garbage collected like objects are. You'll have to remove them from the dictionary yourself. You'll also have to maintain a unique ID for each node so you can concatenate them to a key representing them both together. Dictionaries also can't easily represent directed edges or parallel edges (when there are multiple edges between the same pair of nodes).

I think using objects would be cleaner and more flexible, because C# can automatically take care of a bunch of the management stuff for you.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Okay please check my new comment on another way I tried to solve this and please let me know if that could work \$\endgroup\$ – ckzilla Oct 3 '14 at 16:53
  • 1
    \$\begingroup\$ @JimZilla Alright, I added a section at the end to discuss that a bit. (If you'd like to get more detailed about the implementation, it would be better to start a new question on StackOverflow, where general programming is on-topic.) \$\endgroup\$ – Anko Oct 3 '14 at 17:34
  • \$\begingroup\$ Thanks a lot. Makes complete sense now :) I will implement it using classes. \$\endgroup\$ – ckzilla Oct 3 '14 at 17:48
-1
\$\begingroup\$

Have you tried to create your own class/struct to represent the nodes?

You don't tell much about what your nodes are but with a Node class made by you you'd be able to stock anything you need inside and still use it as Dictionary key.

That way, when you walk through your dictionary you can always know Nodes weight.

But you can also save the list of adjacent nodes in the Node class too making the Dictionary useless. If every Node is in charge of knowing its weight but also of knowing its neighbors everything can be saved in a simple List or Array.

I hope it helps.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ This answer could be improved by actually demonstrating the technique you're talking about, since the asker is wondering where/how to store weights and all you're really telling him is "store them someplace." \$\endgroup\$ – user1430 Oct 3 '14 at 16:02
  • \$\begingroup\$ Sorry @JoshPetrie I though my answer was clear enough with "...but with a Node class made by you you'd be able to stock anything you need inside and still use it as Dictionary key..." \$\endgroup\$ – lvictorino Oct 3 '14 at 17:35
  • \$\begingroup\$ yes that should work too. thanks. I will try that out \$\endgroup\$ – ckzilla Oct 3 '14 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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