How should I store edge weights for my A* graph?

Question

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?

Answer 1

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.

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.

In the above,
blue squares are vertex objects, red circles are edge objects, arrows are references
vertex A's list of outgoing edges is [ E₂ ]
vertex B's list of outgoing edges is [ E₁, E₄ ]
vertex C's list of outgoing edges is [ E₃ ]

---

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.

Answer 2

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.