futuredib

Mostly what I have about our graph implementation is that we should use a vector-like structure to store nodes and edges.

Why?

Most of the time graphs will be loaded during the begining of the applycation and they will rarely change during the game. This means, we will only add nodes and edges once and almost never erase them. This unless a bridge explodes, an avalanche blocks a way or a door opens(and even in this case we can mark those edges as blocked or unblocked without erasing them).

This means, most of the time, almost every second we will be performing searches over the graph.

Vectors are known for their slow adding/erasing performance but very good searching performance becuase they maintain all their elements within the same memory block (this helps with element indexing).

I am not saying I will use vectors, but something like that. I have to explore what structures CS offers for me to use :). Maybe you can give me some ideas on that.

Besides from that, I think graphs should be aloud to be defined dynamically (by an automatic graph generation algorythm) and statically (defined in world files).

I have some ideas on dynamic graph creation, these are:

Polygonal Meshes
The level is made of polygons connected to other polygons. Each polygon acts as a node in the graph. Nodes are connected if their corresponding polygons share an edge

Dirichlet Domains, also known as Voronoi Diagrams
Graphs can be defined by Dirichlet domains by defining a set of points (called characteristic points) in the level which will serve as nodes. Each node has a region of influence around it, and it is connected to all other nodes within its region of influence.

Points of visibility
I am short on time right now, but I will add a description, later ;)