A couple of weeks ago I had a very strong image of a particular type of map editor for Subversion, that would be extremely easy for me to create, and (far more importantly) extremely easy for pretty much anyone to use. I was thinking about older games like Dungeon Keeper, and newer indie stuff like Dwarf Fortress, and they don’t bother with any complex geometry – they restrict the whole game world to squares, and do everything on a grid. It’s like drawing on graph paper, and every square can be empty or it could be a wall, or water, whatever. Initially this might seem extremely limiting, but both of those games manage to exhibit lots of possibilities to the player and don’t feel particularly restrained because of their grid like nature. I decided to run with this concept for a while and threw together a simple graph-paper prototype in a few hours.
It’s actually a lot of fun to use, and you can build quite complex geometry extremely quickly. Left clicking/dragging creates a room, ie an empty space with a 1 square wall around it. You can hold the shift key to fill the area with solid wall, and you can hold the ctrl key to delete whatever is in your dragged area. You can just left click on any square and doodle freehand if you like. In a possible future version, you could rotate the camera to be facing one of the walls and you could use the same mouse moves to cut out a window, a door, whatever you wanted. This system could also be easily extended with 45 degree angles, so it doesn’t have to be locked down to a grid. Dead simple, lots of fun to play with – both excellent properties of an editor designed with user-made content in mind.
I felt this was a pretty good prototype, but I could already see the technical limitations. Lets say for example you have a grid of 100x100, and each cell represents 1 metre square, that gives you 100 square metres, but the bad news is that all your walls have to be one metre thick. I’m not currently planning on setting the game inside NORAD or inside a dwarven fortress, so this clearly isn’t acceptable. But if you make your cells (say) 10cm square, then a 100x100 grid gives you just 10 square metres to play with, which isn’t big enough for anything. Why is the grid limited to 100x100? Because we’re rendering the world on a cell by cell basis, a 100x100 grid is already giving us 10,000 polygons just for a flat surface. Ultimately if you want large areas but the ability to edit fine detail, you can quickly find yourself blowing the whole render budget on geometry that’s no more advanced than D-Generation.
I quickly realised this was a stupid way to go, and set about working on an improved version using Quad Trees. Quad Trees are related to BSP trees commonly used to get FPS games running at a decent frame rate, and basically give us a nice way to partition the world so that we can have big empty areas that use up very few polygons, but still have the extremely high detail exactly where we need it. If you imagine a 100 metre square area, a quad tree would recursively divide this area into 4 blocks of 50 metres square each, one in each quarter. Each of those blocks would be further divided into 4 blocks of 25 metres square each. You can continue this subdivision all the way down, until you end up with areas that are just 10cm or even less in the areas where you need the detail. This is a much more efficient method of storing the same geometry, and is much quicker to render. This screenshot shows the same system, with red lines to represent the division of the world into a quad tree.
So four paragraphs and two pictures later, why am I still banging on about this when it’s clearly so limited? This method actually has some serious advantages over any modern system that are not immediately obvious. For example, the scenery is completely dynamic – there’s no need for any pre-computing, you can render everything via the quad tree extremely fast. You could blow the walls down with explosives or drill holes through the roof from one section to the next – genuinely dynamic game geometry for free. You can also render the world in correct back-to-front order, meaning you can do transparency without first having to depth sort your geometry. I tried to do this with the existing system a while back and concluded it was impossible without generating a BSP tree first – an extremely slow process that results in static geometry. Ray casting in this system is extremely fast – meaning you can do realtime shadows over everything for very little cost. Ultimately though, the biggest benefits are for the user – editing a world in this way is extremely simple and intuitive.
There’s already an example of a first person shooter that has been built using this core idea – and it’s called Cube. If you’re still thinking this form of map editing is very limited, I suggest you have a look at some of the game maps in this game.
http://cubeengine.com/
To really hammer the point home, while playing Cube in a Multiplayer environment you can press E to open the map editor and start building new geometry, and other players will see it too. You can knock down walls, build new ones, whatever you like, in real time. Try doing that in Unreal and see how far you get.
Here's another example showing what you can achieve if you take this to extremes. This is a Voxel demo using very similar (but more advanced) concepts, with completely destructable terrain in 3d space. This is from Ken Silverman, author of the Build engine used in Duke 3d et all. This demo also uses ray tracing to render the world, rather than polygon rendering - which probably makes more sense (it makes the polygon limit go away) but it's just not how modern graphics cards want to operate.
http://www.advsys.net/ken/voxlap/voxlap03.htm
Ultimately I’m not totally sold on the idea, because although you can approximate complex geometry, you can’t really do anything with totally weird angles. Looking at the pic of the doom map above, this sort of map would be extremely difficult to emulate in a grid based system. But I also know that perhaps ten times less people will be willing to edit maps with the kind of system that leads to doom maps like the one above. So ultimately some kind of hybrid may be the way forwards – using the grid system as a scratch pad for quick and dirty editing, and converting that into a more complex system if the user wants to.
On a totally unrelated note, today is 24th March, which some of our hardest-core fans might recognise as the starting date for Uplink (2010 of course). It also happens (not entirely un-coincidentally) to be my birthday, which makes me 29 today – just 12 months to go until the scary big Three Oh. I already own the slippers, and the dog is looking more and more likely every day.
