Friday, June 8, 2012

rounding some corners

I've been quiet the past couple of days. Some of that is due to some amount of Skyrim playing.  Much of the rest of the time has been spent on a couple of key features in the maze game.

I wanted to add a surface distance heuristic to use for the A.I. and maybe object placement. I generated a list of test cases using PICT, wrote a quick perl script to add curly brackets and commas into the output, which I then pasted into some code to use as input for a fairly simple API-type test with some error checking and logging. This script got attached to a dummy object in a scene cloned from the one I use for the main game. Working with the data structure I use for “cube space” requires the object I use for the cube itself, which defines how big the cube is and thus how big the array for storing the generated data needs to be and all the edges and faces wrap around to each other. Distance is measured as a line wrapped around the surface of this cube. Spanning multiple sides of the cube is a less-than-simple special case of this that I would expect to occur quite frequently.

Since we work in real space, and are not trying to generate things in a certain way with the edges, the shared edges idea is completely absent from distance computation. Instead, I created a new delegate table, using the same component operations I refactored from the edge wrapping code used in maze generation, only here the wrapping is more explicitly from side X to side Y instead of from one type of edge to another. I do this because it is possible for this function to have to completely wrap around to the other side of the cube, so transitions from any one face to any other face need to be taken into account. What's more, wrapping around to the other side can be done in four possible directions, of which I select the shortest one. Depending on the direction taken, the wrapping may occur in one of two different ways –  the same opposite face wrapped vertically will appear inverted relative to if it were wrapped horizontally. This occurs very subtly in the game and is by design to kind of throw the player off a little bit –  the maze appears to shift but it's exactly the same, just from a different perspective.

So the distance function uses this table, which effectively “rotates” the destination face, if we're finding distance across sides, so that the local coordinate system for that face, when viewed as a flat, unwrapped linear space, lines up with the source face, making a straightforward linear distance computation possible. If the distance span is only to an adjacent face, the above transformation is performed and the distance is computed –  pretty simple. If the distance span is over to the other side of the cube –  two faces –  the same thing is done four times –  one in each of the four possible directions, and the minimum of these is returned.

It took a while to wrap my head around this, but the resulting ~60 lines of code (37 of these are the delegate table) came out pretty elegant looking. There were a few test failures that I had to work through and debug. These were relatively easy thanks to the prefactoring I had done using the 15–line rule and SLAP.

The next thing on my list was to make the randomly generated mazes a little more interesting to navigate and a bit more suitable for pac-man-esque player-chased-by-AI gameplay. What this means is there can be no dead ends, because this would complicate the “ghost” AI and would also create some nasty surprises for the player quite frequently. I want the player to have fun playing the game, while still being challenged. There may still be some nasty surprises lurking around a corner, but I'd like to make it as much as possible such that a skilled player can either deal with these or avoid them altogether.

The first approach I took was to just randomly pick some walls that had exactly two open spaces on either side and remove them. The chance of removing a wall could be adjusted from a public variable. This did work somewhat, but I still had dead ends, which suck. So, I wrote a small helper class to remove the dead ends. It literally goes through the generated maze, and if there's only one open adjacent space, it sees that as a dead end, and opens up one of the other adjacent walls. Problem solved. Occasionally there are some “loner spaces” that are the probably the result of some kind of bug I haven't yet tracked down in the maze generation code. These will slip through the dead end catcher, so I added a little extra code to also detect these in the same pass and just add an extra open space.

So now I've got randomly generated mazes with no dead ends. One other thing that I had in the original LD23 game that I haven't added yet is the rounded edges. Everything has just been solid cubes up to this point. I have what I think is a pretty straightforward solution. I'll see if I can implement that today and maybe also see if I can also do some mesh-optimization work later tonight. The actual A.I. code might be a little bit more involved. There's a couple of other key pieces to that I will have to figure out and implement solutions for. I'll also need to block out some time this weekend to go to town with the sound effects. I'm putting that off until I've got a more or less completely playable level to the game functioning. I'll probably also start soliciting people for beta testing around then, so feel free to e-mail me if you want to get in on that.

No comments:

Post a Comment