Graph
From GPWiki
The wiki is now hosted by GameDev.NET at wiki.gamedev.net. All gpwiki.org content has been moved to the new server. However, the GPWiki forums are still active! Come say hello. A graph is a basic mathematic concept meaning a collection of points with lines between them. Graphs can have diverse meanings, but a common use of them is to represent points in space and the connections between them. If you take a number of cities near you as the points (nodes), and the important roads between them as the lines, you've got a graph. There is also such a thing as a weighted graph, where each line has a 'weight' attached to it (in the previous example this would be the length of the road). Graphs may sound simple, but there's a whole field of mathematics associated with them. There are many neat (and some actually useful) tricks you can do with them. See A* for an example. Below is a simple graph:
And above here is an example of a weighted graph. Note that the weights are arbitrary, they do not have to adhere to a certain scale or rule. The weights between points in the graph may have any meaning necessary. It could be a measure of distance, a measure of time, the average number of african swallows that travel between these cities in a given eon, etc. The weights only matter in the mathematical algorithm that is applied to the graph, such as in Dijkstra's Algorithm. |
The Game Programming Wiki has moved! 
