I’ve been thinking I should be trying to keep this site updated weekly, so heres my next “exciting” installment :P. I’ve been making some good progress on my Windows Phone 7 game, with the beginnings of a decent relatively efficient and easy to use engine. I’ve moved away from the engine for the time being however, and I’ve been developing a tool for level creation. I wanted something that would allow for easy level building as the intention is to have a lot of 5-10minite levels. Without a simple to use tool I’d be spending all my time designing levels, and no time actually building the tech – I’m a programmer, not a level designer!
So with ease of use in mind I decided that something tile-based would be a good approach and means that I can use a third party tool for the building interface. I quickly settled on Tiled as it seems to be about the best tile-editor out there. Tiled is a nice clean and simple tool that can generate tile-maps for litrally any size of map, which is good as I’m still not all that sure how big my maps will be. I’m imagining they’ll be pretty big as the game should progress pretty fast. Its also free to use which is of course important ;-). Tiled can be found here. Heres an example of a very small test map I’ve been using.
With a map editor, I then needed some way to convert this to something I could use in game. First of all I don’t want the game to be 2D so the 2D tile-map needed to be converted into a 3D mesh. Second of all i don’t want the game to look like its tilebased, so this meant altering the mesh to de-tileify it. I delt with the latter simply by rounding all the corners, and its worked pretty well. I’ll be doing more to de-tile it, but more on that later. The former however was alittle more chalenging.
I had two options. First of all I could convert each of the tiles into a 3D respesentation and have a tiled approach. Then for rounding the corners I can simply find the corners and chop a part off. The other option was to figure out the boundries of the map and then use a tessellation algorithm to calculate the mesh. The second option is significantly harder so I went with the first.
This tiled approach worked successfully, and I managed to end up with a nice looking level map. There were problems however. The first and more minor was that it was proving difficult to smooth off concave angles in the map. It wasn’t impossible, but I couldn’t get it working and I bailed on it it due to the next problem. This approach led to a huge number of triangles in the mesh. The tiny tiny example map ended up having 716 vertices and 1056 indices. Thats 352 Triangles. Okay that doesn’t sound like much, but when you consider that I’m expecting my level maps to be 100x bigger than that I’m sure you can see the problem. My previous post reflected on the fact that the phone was capable of rendering quite large numbers of triangles, however those were in test cases and wont apply to a full game. I’m estimating that I’ve got 10000 – 15000 or so triangles to work with for my entire scene, so I don’t want to be wasting half of that on just the ground. The following are some screenies of the ground built using this method – one with solid shading, and one wireframe to show of the nice pattern ;-)
With this deemed as a no-go, I then considered the tessellation method. I’d previously written an ear-cutting tessellation algorithm at Realtime Worlds for tessellating roads. I couldn’t quite remember how it worked, but I found a good paper describing an implimention which was enough to jog my memory. The paper called Triangulation by Ear Clipping by David Eberly(I’m faily certain I’ve also read a paper on physics calculations by him. He’s clearly a knowledgable man :P) can be found here. This meant the actual tessellation part wasn’t so difficult, but when I’d implemented this before I did not have to generate the outline data. This proved quite a challenge. I eventually settled on a method where I would simply find the most top-left tile in each polygon and work anti-clockwise arround it noting each corner. I would then do the same clockwise for each hole in in the polygon. I then calculate the nearest point in the outer polygon to the start of the inner polygon, and slot the inner polygon in here. This successfully leaves a simply polygon that can be tessellated due to winding the inner polygon the opposite way to the outer. What we end up with looks something like this(Note, this graph is for a different input map. I built this for debugging and couldnt be bothered building annother for the updated map):
After all that I then proceeded to pass this to my tesselation algorithm and like magic a level mesh is produced! This producted far greater results. 60 vertices, 174 indices which comes to 58 triangles. Thats 6 times less, meaning 6 times bigger levels! There are potential problems however. The algorithm outputs alot of long thin triangles, which I believe less powerful hardware can have trouble texturing correctly. I’ve not yet got any output from the tool that I can load into the game on device, so I’m not all that sure how the phone will handle rendering it. I’m hopeful however, and there are ways i can ammend the algorithm to try and create wider angles on the triangles. Again heres a solid and wireframe representation.
So thats some good progress this week. There are still alot of things that need to be done to the tool before its finished however. First of all I need to break the level polygons up into a grid so that I can omit sections that are offscreen when running on the phone. I also need to do some improved de-tile-ifying (which is totally a word :P) and add a border to the edges. The borders will appear to be rounded and should make the level mesh look significantly more 3D(since at the moment it is completely flat… not much change from 2D :P). I plan on baking lighting into the level mesh here and allow for scenery objects to be placed and batched into the level mesh. Finally, I’ll be adding functionality for processing object start positions and such so enemies and pickups and whatnot can also be added to the level through Tiled.
Anyways, this has turned into one mamoth post, hopefully someones actually endured and made it this far :D. My next week at work is going to be crunch-tastic, so I probably wont have as much to write about, but hopefully I’ll have made at least alittle progress :)
