Structure of Astar (A*) graph search data in C#

Question

How do you structure you graphs/nodes in a graph search class? I'm basically creating a NavMesh and need to generate the nodes from 1 polygon to the other. The edge that joins both polygons will be the node.

I'll then run A* on these Nodes to calculate the shortest path. I just need to know how to structure my classes and their properties?

I know for sure I wont need to create a fully blown undirected graph with nodes and edges.

Answer 1

All you need for A* is the ability to take a node and from it efficiently extract a list of its neighbouring nodes. If you already have some data structure that is keeping track of what edges are in what polygons then that seems straightforward; just write a function that takes an Edge and returns IEnumerable<Edge> by extracting that data out of your existing data structure.

Answer 2

Check out this series about the A* algorithm on Eric Lippert's blog. He explains, among other things, what data structures you need