Contents
Can a graph search algorithm understand a grid?
Graph search algorithms don’t really “understand” the layout or properties of a grid. They only understand the connectivity. Pathfinding algorithms that can harness the additional properties of a grid can run more quickly than regular A*. I’ll explore that in another article. Let’s see how to encode a grid in graph form.
Can a grid be viewed as a special case of a graph?
Yes: a grid can be viewed as a special case of a graph. This article is an introduction to the parts of graph theory we use in graph-based pathfinding algorithms, and how grids are represented. A graph-based pathfinding algorithm needs to know what the locations are and also which locations are connected to which other ones.
What can you use graph search for in a game?
Although graph search is an obvious match for pathfinding on maps, you can also use it for lots of other problems. You could represent rooms (nodes) and hallways (edges) in a dungeon exploration game. You could represent players (nodes) and their friendships (edges) in a social game.
How are the vertices of a graph connected?
A mathematical graph is a set of nodes and edges. The nodes (also called vertices or objects) are connected together by the edges (also called links or connections or arrows or arcs). For any graph we need to know two things:
Can a graph have more than one edge?
A graph can have edge B→C without having edge C→B. A multigraph can have multiple edges between the same nodes. Being able to swim across a river or take a raft across the same river is an example in games. Node B could have more than one edge B→C leading to node C. In addition, you can annotate nodes and edges with extra information.
How can I draw on virtual graph paper?
Virtual Graph Paper Virtual Graph Paper is a web application for making drawings and illustrations on a virtual grid. It’s free, and you can use it right here in your browser. Your drawing can be downloaded as a PNG or SVG file, or shared online using a unique URL.