I Want to See Less Walls!

It has been way too long for an update.  I started this update in October and got sidetracked.  Let me finish up and give you what I was doing then.  Life has gotten in the way including my wive’s cancer returning, deciding to write a book for NaNoWriMo (there went November), general work life, and the usual holiday craziness.  But work on A&A has been continuing and I’ve returned efforts to working on it again.

When we last talked, I was trying to decide what to do about high resolution graphics.  I had my doubts, but since then I’ve been working on the OpenGL port of the game.  Overall, this looks good, real good.  The following is a discussion of my work on it.  When I get irritated with the graphics, I go over and work on A&A Classic bugs.  And when the bugs irritate me, I return to the OpenGL port.  Generally, I stay irritated.

Walls 101

So, the first step I decided to take was just to get the basic walls of OpenGL drawing the level.  I was not even sure how to load the graphics, so I spent some time just making an artificial test pattern.  Working out the math, which was really hard as I had to keep walking into walls until I got my XYZ coordinates figured out, I was pretty pleased when I got the basics working:

The weird red dots were used to ensure I was getting the orientation correct.

The above has mip-mapping turned off and uses a “closest” pixel algorithm provided by the OpenGL driver itself.  You can see the lines start to disappear in the distance.  Luckily, turning on mip-mapping is a single setting and we get the following output.

Now the details in the distance look great.  There are options for what to do when pixels are scaled to a bigger size too.  Instead of blurring those, in the above I let it just keep the nearest neighbor algorithm.  This gives something that looks good with textures in A&A and really solves many of the immediate problems I had.  When we get to objects, I’ll just use the options to blur things in the distance and sharpen then up close and keep the pixel look of A&A.

Loading Textures

Next, I wanted to get the textures on the walls.  This was not a real big deal since I have access to all the 256-color uncompressed images.  What I forgot was that all the textures are turned 90 degrees in the A&A resource files and this was turning into a nightmare of confusion as I didn’t quite get my coordinate system right at first.  Eventually, the textures appeared and I fixed my math.  Apparently I was confused on which way was up and I’d jump and all the textures would slide down on the walls.  Very annoying.  Got that fixed.

Doors, oh god the doors!

But the fun with the textures not lining up extended to some very bizarre problems with the doors.  When I would open a door, the texture would slide down the door or stay in place not moving with the door.  That took a fair amount of looking to figure out how I did that.  Come to find out, it was a simple positive/negative calculation on the offset of the door AND a problem again with my coordinates for the textures not being properly referenced by the bottom of the door instead of the top of the door.  Flip, flip, it works now.

I Can See All Rooms

Although I still have no floors, ceilings, or even objects, I started roaming the different levels and checking out how it looked.  The next problem is shown best in the following picture.  This is supposed to be a simple T intersection.  There should be only 3 walls in the view:  A back wall, a left wall, and a right wall.  Instead, I can see all those PLUS the many wall pieces of the next room over and probably even more behind that.

Sometimes this view would appear, sometimes it would not.  Although not easy to show, I could take a few steps to the left and some of the errant walls would disappear.  Go a couple steps to the right, and those walls would disappear and another set may appear.  The problem is that I need these walls NOT to be drawn.  The more that is drawn, the slower the game engine runs.  What is worse is that when the ceiling and floor textures are added, it will cover over all the background rendering and hide the fact the walls were even drawn (good thing I walked around and checked it out first!).  Although these levels are simple, I’m sure people will push the limits of the engine and wonder why some simple corridors are so slow.  We got to fix this.

A new way to track wall coverage

 The problem turned out to be I had two math systems.  One math system was the old game engine’s method of handling wall coordinate calculations.  The second is OpenGL’s coordinate system.  I was trying to use a mix of them, but they just don’t line up.  So, in effect, there were cracks in the wall that would allow the renderer to think it could see through the back wall and it would render the next room over.  What I had to do calculate the very exact coordinates of each wall as determined by OpenGL (I found some code on how to do this online).  Then, I rewrote the occlusion hiding code in the A&A engine to work differently.  In fact I had always wanted to do this and put in a better system that works even faster.  The old system worked good enough for 320×200 resolutions and used a vertical wall slice marking system that would get slower as you went to higher and higher resolutions.  Instead, I changed it to use a “left/right wall range segment” system.  So, instead of marking vertical slice by vertical slice where the back walls are, I now keep track of a list of pairs like (5, 200) that says all vertical slices from 5 to 200 are solid.  It actually is pretty cool because I can now look at the first pair and when it was (window left, window right)  I knew the wall rendering is complete.

Once this new system was in place and the bugs worked out, it started working like a champ.  Here is what the hallway looks like now.

The Subsectors are a Lie!  Ceilings and Floors

We are now ready for floors and ceilings.  I thought this was going to be the easiest part, but it turned into the hardest step of all.  Yay!

The real reason:  Subsectors are a lie!  They are not completely enclosed segments!  Okay, for those of you who may not know, a sector in the engine is any area that has a common floor height and ceiling height.  It is easy to think of the world as made up of polygons of any shape: squares, trapezoids, 10-sided circles, stars, etc.  Whatever you can draw with continuous lines makes a single sector.  Again, they just have to have the same floor and ceiling in common.  Because these polygons can be ANY shape, when the level is saved, it creates something called subsectors which tell how to break up the sectors into smaller pieces.

The problem is — I forgot how subsectors really work.  As I was gearing up for this, I naively thought that subsectors would just be convex polygons with all their lines and walls determined.  Not … exactly.

Let’s see if I can explain it a different way.  Take a piece of paper and call it the map.  As you walk through the BSP tree looking for where a (sub)sector is, you go through a list of wall segments saying if the subsector is on one side of the wall or the other.  So, imagine taking scissors and cutting the piece of paper in half along the wall segment (a good BSP is always cutting the paper in half each time).  One half is discarded and the other half kept.  Continuing the BSP tree walk, you get another wall segment and cut the paper again roughly in half.  Keep going until you get to the end of the BSP tree and you end up at a leaf of the tree where the subsector definition is. The subsector definition now contains the last list of cuts you need to make to shape the remaining paper into the proper subsector shape.  Again, these cuts are always full lines across the paper.  The bad news is that these last subsector “cuts” are not a full definition of the polygon but what cuts are needed in addition to all the other BSP tree cuts to make it.  That can be some 10 to 20 cuts!

If you did this correctly (i.e. always make full cuts across the paper), you will always have a convex polygon in your hand.  The final shape is a piece of a sector — also know as the subsector.  Many times this will be a square or triangle, but it really can be many other bizarre shapes — just always convex.

The great thing about convex polygons are they are very easy to render.  I won’t get into all the details, but they’re fast and simple.  This all sounds great until you realize that I’ve had to a do a TON of processing just to draw a SINGLE PIECE of the floor or ceiling.  The view can be hundreds of these!

And, the strange thing is that the original A&A game engine does NOT draw the floors and ceilings with polygons.  Instead, it would look at the vertical strip above and below a wall and draw the appropriate texture until it bumped into a new wall piece.  It was more akin to a flood fill algorithm than a polygon renderer.  And the beauty of it was it would always fill the screen.

So, what did I end up doing?  Because computers are much more powerful today, I wrote all the code necessary to calculate each and every subsector polygon when the level is loaded and store it in memory.  Done!  Now when I walked the BSP to determine which walls to draw, I would just draw all the subsector polygons as well.  Since they are precomputed XY lines, I just add in their current height, throw on a texture and BOOM! there it is.

Well, almost. The above picture shows the floor was added (ceiling not added yet).  Lining up coordinates between the textures (particularly the non-square ones) turned out to be challenge.  As you can see, the textures were not working right.  Okay, BOOM!

Fixed that.  Got the textures in place, added the ceiling, and made sure it all works on moving doors.  Then, I fixed the shading on the walls for the lighting levels.  Looking pretty good and runs fairly fast at high resolutions.  Nice!

What’s Next?

I still have some basics to get back in there.  Obviously, I still don’t have objects in the world.  I still have some issues with transparent walls (ones with holes in them) and translucent walls (ones that blend in their background).  I also have some nasty white dot issues.  I left the initial background white and there are times when the background is peaking through the walls.  That means I’m not covering every pixel of the scene properly and will have to check some math and look into some “stitching” issues.

And there is the sky issue and the crash when you click on the world and the …. I’ll save that for an update next time.

What do you think?  Looking good?  Click on any of the pictures to enlarge them.  If you got tips will dealing with the stitching problem, I’d love to hear how you’ve dealt with it.

Oh, and for the music lovers out there, try this long piece out:  Andy Pickford – The Sentinel