Collision detection makes the world feel solid
Sunday, 21st November 2010
One of the larger problems with the 3D engine for the TI-83+ calculator series I have been working on is that it's possible to move the camera through walls. This doesn't make the world feel especially solid, so I've started working on some collision detection routines.
Work commitments have left me with little time to spend on this project over the last couple of weeks so progress has been very slow, but I've got a basic collision detection system mostly working.
I spend most of the above screenshot running into walls. The code seems to work relatively well and quite quickly, though it's far from perfect. The still image shows the new settings screen, which is hopefully a little easier to use than remembering which keys do what. It also has the advantage of displaying the state of the current settings.
The walls are stored as line segments between two 2D vertices, and the collision detection has to ensure that the player does not get too close to any of these walls. The technique I have used starts by calculating the closest point on the line to the player.
The above image shows a wall (the solid line segment) and three possible player positions (the heavy dots). The arrows point to the closest point on the wall's line. The closest point on the line to the top player position is past the end of the line segment, so it is ignored. The other two closest points lie on the line segment, so these are checked in more detail.
The distance between the closest point on the line and the player position is then calculated and compared to a threshold value (the radius of the player). The above image highlights the out-of-bounds region in tan. The lower player position is outside this region so is ignored, but the upper player position is inside it and needs to be corrected.
The correction is quite straightforward. We know the closest point on the wall to the player. The angle of the wall's normal is stored in the level file, so we can easily calculate a vector from that to push the player a fixed distance away from the wall.
In addition to the above 2D checks, a very simple height check is performed for "upper and lower"-type walls. These are walls with a central hole so you can pass over or under them, and are used to connect sectors with varying floor and ceiling heights. The top of the player's head is used to check the ceiling height. Rather than use the height of the player's feet to check the floor height their knee height is used. This is to allow the player to climb low walls (such as the edges of steps).
When I first implemented these collision detection techniques I checked every wall in the map. This halved the framerate in places, and as the framerate is not particularly high in the first place I needed to find a way to reduce the number of tests. Taking further inspiration from DOOM I implemented a "blockmap". This breaks the map down into square blocks and each block contains a list of which walls pass through it. To perform collision detection I look up which block the player is in and from that I can retrieve a reduced list of which walls they may end up walking into. The original implementation had to check well over a hundred walls for each movement; the blockmap reduces this to 26 in the worst case scenario for the current level design.
Sadly, this additional blockmap enlarged the size of the map quite a bit, so I've attempted to reduce it a little. For simplicity and performance most structures referred to other structures by pointer (for example a sub sector contained a list of pointers to walls and each wall contained pointers to a front and back sector). I've changed most of these to now refer to other structures by index, which shaved a few hundred bytes off the map at the cost of a few hundred clock cycles. Overall performance still isn't great, though I haven't found it noticeably slower than the previous demos.
I added very primitive physics for moving the player up and down relative to the floor to complement the collision detection. This retrieves the floor height from the sector directly under the centre of the player and compares it to the current player height. If the new floor height is higher than the old floor height then the player's foot height is set to a point half way between the two; this smoothes the animation slightly when climbing up stairs (rather than just snapping to the new floor height). When moving from a higher floor to a lower floor the player's downward speed is increased to roughly simulate gravity.
A demo for the TI-83+ series and TI-83 can be found in Nostromo.zip. As always, this is a piece of software in development and there may be calculator-crashing bugs, so please back up any important files before running it.
Enlarging the world
Sunday, 7th November 2010
There have been very few changes to the features of Nostromo recently. I have tried a number of ways to optimise the performance and whilst the handful of micro-optimisations I have made have boosted the frame rate a little none of the higher-level optimisations have done much. I did try, for example, storing a bounding box around each BSP node and ignoring it (and all its children) should this bounding box fall outside the field of view; the additional code to check the bounding box ended up halving the framerate rather than improving it.
I have, however, enlarged the level quite considerably. A staircase connects the central room with the pit to a rather strangely-shaped arrangement of walls (again copied from E2M7). The room with a pit continues to cause issues; looking across it towards the room with the small central staircase forces the engine to step through a very large number of convex sub-sectors and check many walls. This drops the frame rate down to about 3 FPS on a TI-83+. However, this is specific to that room; the newly-added rooms have not noticeably affected the frame rate in other parts of the level.
Another minor improvement is that the engine now supports different sprites. I'm not too good at drawing them, as you can probably tell from the above screenshots, but at least the code is there to support them.
You can download a TI-83 and TI-83+ binary to try the demo on your calculator (please back up any important files first). Alternatively, here is an animated screenshot.
Adding sprite objects to the 3D world
Tuesday, 2nd November 2010
The previous entry showed a room from a map copied from DOOM's E2M7. I have since added the adjacent room:
It may not look as interesting as the other room but it is significantly more costly to render due to the sheer number of lines visible at a time in it. Looking across it from the far corner dropped performance down to around 2 FPS on the 6MHz TI-83+, which was really not a very good effort. I spent a fair amount of time over the weekend trying to optimise the code as much as I could, and manage to bring the frame rate in the player's starting position from 6 FPS up to the target 10 FPS. Looking across the length of the new room still dropped the framerate to around 4 FPS at 6MHz, but it's a start.
Once the engine had been made a little faster it seemed a good idea to slow it back down again by adding a feature. I had been pondering how to add objects in the form of scaled sprites to the world. Working out where to put them on the screen isn't so difficult, but clipping them against the world geometry so that they couldn't be seen through walls is another matter entirely. One way that seemed popular is to draw the objects in reverse depth order (drawing the sprites that were further away before those that were closer) and using a depth buffer for the world geometry to clip each pixel of the sprite against the world. This would take up a lot of memory on the calculator and run very slowly (populating the buffer with a depth value for each pixel would be a very expensive operation, as you'd have to interpolate depth values between the ends of walls and edges of floors).
The engine makes use of three per-column clipping tables when rendering the scene. One keeps track of columns that have been completed (usually by drawing a "middle" wall to that column); once completed no more pixels may be drawn to that column. The other two tables are used to define the upper and lower clipping bounds. At the start of the scene these are reset to the top and bottom edges of the display. As the world is rendered from front-to-back these regions are reduced to clip geometry that is further away against geometry that is nearer (think of looking through a hole in a wall — things that are further away from you will never be drawn in the space above or below that hole).
Fortunately, you can use this clipping information to clip sprites against the world geometry too. Each sprite object needs to be associated with a convex subsector. These subsectors are made up of walls and are drawn from front-to-back (sorted by the BSP tree) as the world is rendered. Before each one of these subsectors is drawn it is checked to see if it contains any sprite objects — if it does, the current clipping buffers and a reference to the subsector are pushed onto a stack. When all of the walls and floors have been drawn this stack contains a list of all of the subsectors containing sprites and the clipping regions used to draw those subsectors in front-to-back order. Stacks are Last In, First Out structures and so when you pull the data back out of this stack you end up retrieving a list of sprites to draw and the associated clipping regions in back-to-front order. This allows you to effectively unwind the clipping operations, so as you draw the sprites from back-to-front you can gradually enlarge the clipping regions in the opposite order to the way that they were reduced when drawing the walls. You would still need to sort the sprites manually from back-to-front within each subsector, but for the time being I've limited myself to one sprite per subsector for ease of development.
The above screenshots demonstrate an initial test of the "things" (as they are apparently technically called), rendering them as solid black squares.
Scaled sprites tend to be more useful than solid black squares, however, so here are a pair of candlesticks (well, that was the intention at any rate; call them cacti if you must). The sprite was simply ORed to the display, so pixels could be black or transparent.
I then added support for "white" pixels too. The above screenshot is a link to an animated GIF showing the engine in action. The sprites appear to jiggle up and down and have invalid data drawn underneath them in places, which was caused by my accidentally overwriting an important register before rendering each column (fortunately an easy one to spot)! The relatively high frame rate in the above image was helped by running at 15MHz and using the old single-room map.
The above screenshot (click for the animated GIF) fixes the dancing sprites and restores the second room, though is still running at 15MHz. For a bit of fun I added animated doors; all this does is adjust the floor heights of the sectors used to represent "doors" (pressing Alpha will toggle both doors open or shut) but it makes the world look a little more dynamic.
There are still some rendering bugs in the engine. The above animated screenshot demonstrates one; when close to a wall edge you will sometimes see a temporary vertical line the height of the screen or the screen will flash white. I reckon this is probably an integer overflow issue causing the projected height of a line to be on the opposite side of the screen than the one it should be (the bottom edge of a hole in a wall may be projected above the screen rather than below it, causing the entire screen to be clipped out, for example). One bug that took a while to identify (it only appeared in very particular positions; moving one unit in any direction cured it) was caused by truncating a 32-bit integer to a 24-bit one. When viewing a long wall from a long distance the result of a 16-bit (difference between end and start X coordinates) by 16-bit (Y coordinate of the start of the wall) multiplication was resulting in a value of $00800000 or so (a large positive number). When truncated to 24 bits this becomes $800000, which has the most-significant bit set and was therefore treated as a large negative number. As this was part of the wall clipping code it would end up clipping a wall end a long way behind the camera instead of within the view; fortunately this obvious mistake is easy to spot and correct (the answer can only be positive, so if you get a negative one just negate it).
If you'd like to try the demo on your own calculator please download Nostromo.zip. As this is a work in progress there are likely to be bugs so please back up any important files first!
Adapting a room from DOOM's E2M7 to the TI-83+ calculator
Thursday, 28th October 2010
The level I've been working with as a test for the TI-83+ 3D engine was something I quickly threw together. I've never been much good at the design side of things, and my lack of imagination was producing something very simple that wasn't really challenging the engine and testing whether it could be used in a game. Looking for inspiration, I played through map E2M7 in DOOM and found a fairly interesting room to try to convert.
I'm sure you can tell which is the original room from DOOM and which is my adaptation of it.
Since the last post I have had to make quite a few tweaks to the engine. In the previous build there was a bug which cropped up when the top or bottom edges of walls appeared above or below the screen bounds. This turned out to be caused by a routine that was intended to clip a signed 16-bit integer to the range 0-63; it would return 0 for values 128 to 255 instead of 63. Fortunately this was an easy fix.
Another bug was in the way "upper and lower" walls were handled. Sectors have different heights and "upper and lower" walls go between two adjacent sectors and connect the ceiling of one to the other and the floor of one to the other, leaving a gap in the middle.
The above picture shows the four main types of sector-to-sector transition through an "upper and lower" wall type. Different transitions require different numbers of horizontal wall edges to be traced; in the bottom left example (going to a sector that has a lower ceiling and higher floor than the current one) four lines would be required and in the top right example (going to a sector that has a higher ceiling and lower floor than the current one) two lines would be required. The previous version of the engine always drew four lines, which would produce a spurious line above or below the "hole" for three out of the four different combinations of sector-to-sector transition. By comparing sector heights the right number of horizontal lines can be drawn, which greatly improves the appearance of the world and slightly increases the performance, too.
A less immediately obvious limitation was in my implementation of the BSP tree structure. Each node on the tree splits the world geometry into two halves; one half is in "front" of the partition and the other is "behind" it. Each chunk of split geometry can be further subdivided by additional partitions until you're left with a collection of walls that surround a convex region. You can then walk the tree, checking which side of each partition you are on to determine the order that the walls should be rendered in. For more detailed information the Wikipedia article on binary space partitioning is a good starting place but the basic requirement is that you should be able to slice up level geometry into convex regions with partitions. I had naïvely assumed that horizontal or vertical partitions would be sufficient (and they are useful as you can very quickly determine which side of a horizontal or vertical line the camera is on). However, this room demonstrated that such a limitation would not be practical.
Consider the above geometry. The black lines are walls and the small grey lines represent the wall normals; that is, the walls face the inside of the "Z". The wall in the middle is double-sided; you could put the camera above or below it and see it. However you slice that map up with horizontal or vertical partitions you will still end up with regions that are not convex.
A single partition along the central wall divides the map into two convex regions. I had initially thought that checking which side of such a partition the camera lay would be an expensive operation, but it's not too bad; as a line can be represented by the expression y=mx+c I can store the gradient m and y-intercept c in the level data and simply plug in the camera's x and compare to y to determine the side. A single multiplication and an addition isn't too much to ask for.
Fortunately, there are only two of these partitions in the level!
I have added some other features to the demo program. Pressing Zoom when using a calculator that can run at 15MHz (a TI-83+ SE or any TI-84+) toggles the speed between 6MHz and 15MHz. Pressing Mode or X,T,Θ,n allows you to look up or down. Pressing Window toggles between the default free movement and a mode which snaps you to a fixed height above the floor. These additions are shown in the below screenshot (click to view the animation):
Unfortunately, performance is lousy. Viewing the stairs drops the framerate to a rather sluggish 6 FPS when running at 6MHz (most of the above screenshot is recorded at 15MHz). The LCD's natural motion blur helps a little (it feels a lot more fluid on the calculator than it does on a PC emulator) but I'm aiming for a minimum of 10 FPS, so I need to make quite a few optimisations. There are several low-level ones that could be made; for example, when clipping the 2D line segments to the display I'm using a generic line clipper that clips the line both horizontally and vertically. As wall has been clipped to the horizontal field of view by that point I only really need to clip it to the top and bottom edges of the display. There are also some high-level optimisations to be made; for example, double-sided walls are currently stored as two distinct walls with the vertex order swapped. This means that to handle both sides of the wall the engine has to clip and project it twice, which involves lots of expensive divisions and multiplications. The results of these operations could be cached so that they only needed to be calculated once.
A TI-83 and TI-83+ binary is available if you'd like to try the demonstration on your calculator: please download Nostromo.zip. The usual disclaimers about backing up your data before running the program apply!
Varying wall heights in a 3D engine for the TI-83+
Monday, 25th October 2010
I've done a little more work on the 3D engine for TI-83+ calculators that I mentioned in the previous entry. The main difference is in limited support for varying the heights of floors and ceilings, illustrated in the following screenshots.
Walls now refer to one or two "sectors". A sector is a 2D region of the map of any size or shape; it can be concave or even have holes in it. Walls are also grouped into convex regions named subsectors for rendering purposes. Each wall has a sector in front of it and a sector behind it; these sectors have a specified floor and ceiling height. There are now two types of wall; a "middle" wall which connects the floor and ceiling of the sector in front of it and an "upper and lower" wall which connects the ceilings of the sectors on each side and the floors of the sectors on each side.
This makes occlusion a little trickier and determining where to draw lines around the edges of walls even more so!
The previous version of the renderer worked by drawing walls back-to-front, clearing rectangles the height of the screen behind the wall segments as they were drawn. The first attempt to improve this exchanged rectangles the full height of the screen with trapezia. The screenshot to the left shows the bounding rectangle around each wall segment being filled and the one to the right shows each wall filled as a trapezium. (As before, clicking an image with a border will display an animated screenshot).
Rather than attempt to calculate where lines should be drawn around wall edges I thought I'd experiment with dithered wall fills instead. The left screenshot shows this addition (each wall has a different shade) and the right screenshot shows the addition of support for wall heights (still drawn in the simple back-to-front technique, resulting in significant amounts of overdraw).
Unfortunately, the LCD on the calculator copes rather poorly with dithered fills; the above photograph was taken at the highest contrast setting. Rotating the camera to look at walls with a different dither pattern brings the world back into view. This is rather unacceptable, and is something I ran into with my previous implementation. I think I'll stick to stroked wall outlines rather than filled walls.
I had been experimenting with a new level design in the C# prototype of the engine that added another room accessible via a tunnel from the starting room. I added some code to the C# program to output the level data in a form that could be assembled into the Z80 version. This is shown above, having reverted to a simple wireframe view in anticipation of the new wall drawing code.
The new way to implement occlusion works very differently to the previous one. I had been sorting the geometry from back-to-front and rendering it in order, drawing walls in the foreground on top of walls in the background. This wasn't very efficient and wouldn't scale well. The new approach renders from the front to the back and works on information stored about each column of pixels on the screen. The screen is 96 pixels wide, so there are 96 columns to deal with. A counter is set to 96 at the start of rendering. When a column of a wall is rendered, a flag is set to indicate that that column has been completed and the counter is decremented. When the counter reaches zero, that means that every column on the screen has been completed and the renderer terminates. This is demonstrated in the above screenshot when compared to the previous one; walls that are some distance away from the camera (and behind other wall segments) are not always drawn as the renderer has decided that it has finished before reaching them.
An obvious issue with the above screenshot is that even though some of the geometry is culled, individual walls can still be seen through other ones.
Part of the solution is to use a custom line-drawing routine that checks each pixel against the completed columns table. If a column is marked as completed, the pixel is not drawn; if it isn't, the pixel is drawn. This is shown above.
I previously mentioned that there were two types of wall; "middle" walls (solid ones from the floor to the ceiling) and "upper and lower" ones (these have a hole in the middle). Only "middle" walls flag a column as being completed, as you need to be able to see through the hole in "upper and lower" ones. This causes the rendering bugs in the previous screenshot above and below the holes in the wall. The way to fix this is to add two new per-column clipping tables; one which defines the top edge of the screen and another which defines the bottom edge. These both start at the maximum values (0 for the top edge and 63 for the bottom) and are reduced whenever an "upper and lower" wall type is encountered.
The new code to do this is demonstrated in the above screenshot. There is still, however, a bug in this implementation. The per-column clipping tables are updated by the code that draws the line along the bottom or top edge of the hole in the wall. If this line is partially (or completely) off the screen, these tables are not updated and the rendering bugs appear again (as demonstrated at the end of the above screenshot). A final manual pass over parts of the line that are clipped off the screen corrects the issue:
As can be seen in the bottom left corner of the above screenshot I have added an FPS counter. This is accompanied by code that scales movement by elapsed time so you move at the same speed regardless of how long each frame takes to render. The engine is quite slow (and could no doubt be heavily optimised by someone who's good at assembly) and has quite a few bugs in it but it's certainly looking a little better than it did a week ago. As I only have a regular TI-83+ I'm aiming for something usable at 6MHz; the more modern calculators can run at 15MHz but this feature is not used in the demo.
For those interested in trying the demo on their calculators, click on the above image to download an archive containing a TI-83+ and TI-83 binary. As before, this is experimental and may well crash your calculator, so please back up any important files first!