## Friday, August 20, 2010

### Relative neighborhood graph

I've been trying out various things to improve camera control, but nothing good has turned up yet.

Currently the camera frames the player's rocket and the nearest objective. This can introduce a big discontinuity when a new objective becomes the nearest. The camera controller smooths its motion so it's not horrible but I think I'd like it to anticipate the transfer better. I've been trying out things in a testbed; if you'd like to try it you can get it here. It's a Windows application. Click or drag the mouse to move around; press the space bar to generate a new point set.

A screenshot appears above. The light-colored circle represents the current framing algorithm. The larger circle is an alternate method. What I really want is for it to interpolate between those two solutions so it frames things tighter when it's close to only one target, and then expand so there is a smooth transfer to the next objective.

I've also learned about some cool graphs. The application displays the relative neighborhood graph of the points. I'm not sure if it'll be useful here but I threw it in to see what it was like. It's a subset of the Delaunay triangulation that only contains an edge if there is no third point that is closer to both of that edge's endpoints.

Long, long ago I made a prototype for a game that was ultimately canceled. The idea for the game was that you'd have a map full of towns and villages and you'd help one or the other of a trio of warring factions to conquer all the territory. You'd do this in typical third-person action game format. (It was basically Dynasty Warriors Empires, but about five or six years earlier.) In my prototype I sprinkled towns randomly on the map and then made a Delaunay triangulation to determine which towns were neighbors; the mission generator would use this to generate sortie missions from one to another across the current borders. The problem with the Delaunay triangulation is that you have all these really long edges connecting vertices around the outer perimeter, which wasn't at all what I wanted. This relative neighborhood graph turns out to be exactly what I wanted back then.