Project Proposal – A 3D Map Editor

by Stuart Golodetz

What it is

It’s a program in which you can design 3D maps for games.

Intended implementation language and justification

I’m implementing it in Java, because its AWT toolkit makes for easy UI design, which is helpful when writing a map editor. I could have chosen C++ instead and used something like MFC, but then the project would have been trickier to implement for no good reason.

Why it’s relevant, sensible and worth doing

· It’s in Java and thus relevant to our course in Object-Oriented Programming. Not only that, but the whole idea was inspired by one of the practicals we did in Michaelmas term, which involved a simple box editor.

· It involves implementing a number of things we only had time to touch upon in our Computer Graphics course, like BSP trees, CSG, etc.

· It will involve a significant amount of coding. (So far, over 3000 lines of code have been written. Although a line count only gives us a rough idea of the amount of code involved, 3000 lines is still a lot of code, whichever way you look at it.)

· I feel it’s at the right level of difficulty. It’s something which is challenging, but not insuperably hard. It’s also a segmented project, in the sense that I will be able to implement it a bit at a time, with visible results at every stage. I can therefore implement as much of it as I have time for without feeling under excessive time pressure. Whilst being able to stop at any stage could be construed as a negative point, it’s actually incredibly positive because it encourages you to work until the last possible minute to add new features, without worrying that you’re going to break existing work.

· It’s interesting! I’ve never really got to grips with UI design before and I’ve always eschewed writing a map editor because I felt it was going to be too difficult. Now is the perfect time to have a go at it.

· It’s more than just a toy program! Having an easily customisable map editor will be really useful afterwards when writing 3D games. To date, I’ve been using Valve’s Worldcraft, which is excellent at what it does, but not completely suited to my needs. Writing a fully-featured map editor from scratch will solve my problems, whilst at the same time proving a distinctly challenging project on which to work.

· Even the small amount of work I’ve done on the project so far has shown me that I’m going to go down a lot of blind alleys and have to back up and start parts of the project afresh. This is an extremely positive thing, because refactoring is a vital part of all major projects and it’s worth getting used to it now. Furthermore, I find I’m learning a lot from the approaches I tried that didn’t work. Indeed, they’re providing me with a lot of useful material for my report!

Main features (and comments about how hard I expect them to be to implement)

· Creating and transforming (reflecting, resizing, rotating, translating and possibly shearing) primitive and composite (solid) polygonal objects. At an implementation level, I intend to implement the interface through which such operations can be requested in 2D, by displaying three separate views of the world from different directions. These views will essentially be orthogonal projections onto a pair of axes. [A lot harder than it looks, but mostly done now.]

· CSG operations (union, intersection and difference) on such objects. At an implementation level, this is expected to involve generating BSP trees for the objects involved, followed by performing the actual CSG operations using the generated trees. [Hard to avoid precision problems (even professional editors like Worldcraft have been known to get it wrong if the objects are too complicated). The implementation is intricate, but doable.]

· An interactive 3D view, so that users can “fly” through the world they have created and see what it looks like. I would like to allow object selection (though not object manipulation) in this view, which will involve some sort of picking technique. [I don’t expect the basic rendering of the map in the 3D view to be especially tricky (but I may be wrong!). Allowing users to fly through the world will take a bit of thought and will involve getting to know Java3D rather better, but ultimately should be doable. Implementing picking could get rather interesting. The problem is more in implementing it efficiently than in implementing it by brute force.]

· Loading and saving of maps. [The only fairly trivial part of the editor. I could make life more interesting by writing code to load and save Quake-compatible .map files. The latter might prove tricky because .map files store their brushes as planes rather than polygons and I’m not really sure it’s worth it. Loading .map files, on the other hand, would be very useful.]

Additional ideas (and similar comments to the above)

I’m not intending to implement all of these over the duration of the project, but I would like to find time to put some of the simpler ones in.

· Texture-mapping of polygonal faces. At an implementation level, I intend to allow users to select individual faces in the 3D view, the same way that Worldcraft does it. Unlike Worldcraft, however, I’m intending to allow users to specify texture coordinates individually for each vertex. [This will probably involve something similar to the picking technique used above. I expect the implementation to be fairly intricate. I may have to revise my intention to specify individual texture coordinates, as it may prove a barrier to ease-of-use, in which case more thought will undoubtedly be needed.]

· Landscape areas, implemented using a heightmap technique. [This should be fairly doable. It might also provide a good opportunity to put into practice some of the curved surface techniques we’ve learnt (Bézier surfaces, for example).]

· AI paths of some sort. [This should be doable, but will involve a design decision about how the AI will work for games for which this map editor creates levels. Because AI routing is very game-specific, it would make sense to separate this from the rest of the editor as much as possible, to make it easy to drop in different versions for different games.]

· Level compilation (probably implemented as a separate project, possibly in C++). At an implementation level, I expect this to involve the following stages: (i) CSG union all the brushes, (ii) build a BSP tree for the level, (iii) generate the portals, (iv) perform a portal flood fill, (v) build the potentially visible set (PVS) and (vi) calculate the lightmaps. [CSG unioning all the brushes can be done either before saving the map to a file, or in the separate project itself. I would tend to favour the latter (even though it involves duplication of code), because that way we can have a single file format for the map editor. If we were to CSG union all the brushes, the map would just have one large brush when we loaded it back in! As far as difficulty goes, it’s doable, as is building a BSP tree for the level. Generating the portals is also doable, as is performing a portal flood fill (though you need the level to be completely enclosed for this to work correctly; since you can’t guarantee that users will always create levels which are completely enclosed, you need to check for this). Building the PVS is one of those things that is tricky, but doable, in principle, yet very hard in practice. Precision problems generally rear their ugly head again here. Calculating lightmaps is something that will require a lot of thought. I would be tempted to implement an acceptable Phong lighting model rather than dealing with the complexities of radiosity, but I’m not sure how good the results would be. Unfortunately, I suspect I lack the mathematical knowledge and ability to successfully implement a radiosity solution!]

Screenshots of the prototype version I’ve been working on over Christmas

Figure 1: Spiky gate

Figure 2: Space rocket

References

· The Worldcraft editor; Valve Software.

· Java In A Nutshell, David Flanagan.

· Computer Graphics, Principles and Practice, Foley et al.