Graphs - makingthematrix/gailibrary GitHub Wiki

Another thing I rely on heavily in GAI are graphs. Graphs can be either spatial, or state diagrams. We can think of a spatial graph as a simplified map of the terrain the player and NPCs are located on. The nodes in the graph correspond to points in the 2D or 3D geometry of the game, and they can be used to calculate the closest path between two places, visibility between two points, or they are destinations of NPCs’ movements. That's it: the game's artificial intelligence unit does not need anything more complicated. Walls and other obstacles are modeled simply as the lack of edges between nodes. And if we want to model gravity, ie. that it's more difficult to climb a path than to get down, we can use a version of a graph with weighted one-directional edges (so, one for going one way, one for another). A state diagram is a more abstract entity which help in decision-making. Nodes in the state diagrams may contain tokens. An event in the world may result in transporting a token from one node to another. Then, in another iteration, a function may check the state of the graph and compute a different result because of that change. I plan to create a set of utility methods and traits working on spatial graphs (path-finding, distance computation, etc) and another set for graphs used as state diagrams.

A graph consists of nodes and edges. Each node has an id, unique within the graph, but shared among other graphs. We assume that nodes with the same id in different graphs correspond to different characteristics of the same object. We can, for example, ask the position graph about the node closest to the NPC and a node closest to the player and then we can use their ids to ask the visibility graph if NPC and the player can see each other.

Lots of graphs' methods return ids or pairs of ids (edges) as sets. Then we can perform operations on such sets: A + B (union), A – B (substraction), A * B (the common part), and A ^ B (xor; union without the common part). Since the ids are only natural numbers and I cna safely assume there will be never more than a few thousands of them at the same time there's potential for optimizations of these operations. I ran some experiments and benchmark tests and came up with a specialized USet class, about 3x faster than the Set class from the std library.

Another useful feature in graphs is path-finding. Given two ids the A* algorithm may find the shortest path between them. The result is stored in a hash table, so all consecutive calls will simply use it.

Graphs are complex data structures. I think about creating a bunch of utility methods for creating and manipulating them. Fortunately, in my other project I have dealt with a similar issue when constructing a neural network. I will use some of the same ideas, like builders and default arguments (which in Rust means macros). For example, if you call new Graph(nodes: Set<NodeId>) GAI will create a non-weighted two-directional graph where each two nodes are connected. Alternatively, you can provide only edges: new Graph(edges: Set<(NodeId, NodeId)>) will create a non-weighted two-directional graph with nodes deduced form the edges. This should cover most spatial graphs. For more complex designs you can use a builder:

new GraphBuilder.add(nodeId1).chain(nodeId2).use(nodeId1).chain(nodeId3).build()

A spatial graph is a special kind of graph whose nodes, apart from the ids, have also positions. Two different nodes in a spatial graph cannot have the same position. This means an optimization is possible: If all points were created by a, uhm, PointFactory, it could remember points by their positions and for the same position return the same point, which then would be equal by reference. Not sure if it’s worth, though.

Cell types <- | -> Identifiers