Thursday, July 28, 2011

Yeah, I did it… but wait there is a catch…



Hello again everyone and welcome to another blog regarding Ultima 1 revisited, where I try to figure out how Ultima 1 was programmed and recreate it in assembly from scratch!

So, as of today I finally figured out the movement part as you can see in the video above and it is a lot faster than the previous movement video test.

This was a bitch! I mean, really! REALLY!!!

Working with the DOS TOOL KIT is a very slow and grueling process. Each time you compile your program you have first save the file which takes 5 of so minutes depending of the size of the file! Plus you have to wait about 10 or so minutes for it to compile after you save it. Uhg! By the way, you better save first before you compile because the assembly editor moves the compiler into memory and by doing this it erases whatever program is in memory at the time. Found this out the hard way!

Well as the title alludes to there is a catch or snag in this programming code! Yes I figured out how to move a character around the map, which by the way checks collisions with mountains and oceans! When I was working out the code for the test I only used a small portion of the upper left section of the Ultima map to do my test. Once I realized I was able to get it working I started entering in all the data points for each tile on the map from the left to the right! Well the problem with the Ultima 1 world map is that it is made up of 4 individual maps or kingdoms, which are only access by having a ship.

So let me take you back a few days when I was on cloud nine thinking I’d just figured out how to cure cancer figuratively. “Yes, programming in assembly is that hard!” LOL.

So here I am with a big smile on my face when I start entering in all the tile date values for each map line from top to bottom and I get to about line 24 out of 80! I hit enter to input the line and bam… I get a memory full error! What! Are you kidding me! I’m not even half way with the map tiles, let alone the rest of the ultima program and I run out of bytes! Well, in the midst of committing seppuku I realize I better go to the one source that can bring me to the light! BETH!!

Here is what she had to say in an email I sent her:

Hi Beth,

I bet you never though this email would come but finally I figured out how to move around the screen and it look and feels just like the game.

Funny thing is I didn’t use the method you mentioned where you scroll with the 90% of the existing tiles and just generate the last 10%. I used table look ups and since the redraw is fast enough in assembly I was able to redraw using a column or row shift based on the key pressed. When the key direction is pressed I just re-read the new map tiles and redraw them all on the screen. I know this isn’t the correct method but I tried to work out the other method and kept hitting a brick wall! I will try to work it out but for now it works like it is suppose to. I will post a video very soon so you can see the progress. I’m totally jazzed! This is huge for me and I can now work on the other parts of the game.

Hey, however it works is good enough. When I did my version of U3 I didn’t do the 90% shift thing either, because as you note just redrawing from in-memory tiles can be fast enough. If you don’t need the extra speed, don’t sweat it. You can work out the math on how many cycles per tile it will actually save you to determine how much speed boost you’ll get – I could believe anywhere from 4x to none at all, depending on how you implement the algorithms. Congrats again on getting it to draw!

I do have a few questions if it is ok…

1. I worked out the map and the entire map is about 180 tiles wide X 180 tiles deep approximately. Well, this is a lot of bytes to use and if I calculated right that would need 32,400K or bytes for each tile value!!! How is this possible? The map is huge and basically has 4 separate maps that make up the entire global map. I have to make sure that Richard didn’t use the back side of the disk for game use and put some of the maps on the back side. Even though, how would I put all the individual byte information for each tile to be represented if we are talking 8k for each map and 32k total?

Okay, I don’t know exactly how he did U1, so I’m speculating. I can give you some different approaches to try, though. Conceptually, you should consider the Disk Drive as something akin to a swap file – it’s like extra memory you can use, it’s just slow to read/write so you want to avoid it. That said, what happens is that loads are done at critical points to swap out data files and program code – thus allowing one to essentially be in an entirely different program when in a dungeon, say, than up on the surface.

So, swaps can occur on the surface as well, when you move between maps. That’s one point – so you’d only have to have a single 8k map in memory at a time, and then you’d swap in the new map when you approached the edge of the current one.

Also, how many tile types are there on the map itself? 15 or less? Then you’re wasting a lot of bits. You should make your maps nibble-based. The top 4 bits of any byte are tile A, the low 4 bits are tile B. That means you only need 90x180 = 16.2 k for the whole thing and 4.05k for a single map. And that’s storing it RAW instead of RLE which I recommend against. See my later note for more on that topic.

2. How do you separate assembly code if you run out of space in a certain memory region? If I start my assembly program at $6000 and use the entire free memory range up to $95FF, how would I continue using the rest of memory for my database of tiles?

You separate out your data and routines by how big they are. Then you figure out where in the memory map you want them to go. You then can use Basic to do some like BLOAD to load the individual data/code files into exactly where you want them in memory.

This tile memory usage for the maps is mind bending and I just don’t understand how he was able to put in a database of all the tile references when they would take up so much memory!!!

Another possibility is that he used RLE compression. That will pack it down tremendously. RLE stands for “Run-Length Encoded”. It works like so…

The data is always:

1. A value representing a run of N1 tiles.

2. Type of tile X.

3. A value representing a run of N2 tiles

4. Type of tile Y.

5. Etc.

So if my map row looks like this:

01 01 01 00 00 04 04 04 04 05 05 01 01 01 01 01 01 01 01 01 01

This encodes to (hex here)

03 01 02 01 04 04 02 05 0A 01

And if I’m nibble-based, I can ditch all the zeros and pull this down to:

31 21 44 25 A1

So…5 bytes now take the place of 22.

The longer the runs, the better compression you get. So taking a guess that you get 4x compression, that should pull your maps total down quite a bit. I bet you get better compression than that, especially if you can use nibbles instead of bytes.

Also, if the map uses a major portion of the disk how do I put in the towns, castles, and dungeons? This seem like I don’t have enough space on a single disk but Ultima 1 only comes on one disk.

Compression algorithms. J

Joe

So now I’m at a cross road because I realize I have to change the program I just spent months on trying to get working correctly and I have to utilize a new set of subroutines that will read compressed data strings. This is definitely going to change a lot of my program code.

Well I’m off to work on the problem but while I’m doing that please enjoy the video and if you have any questions please email me at:


I would love to hear from you whether it be comments, criticism, or requests for info, I will try to answer your questions as soon as I can.

Talk to you soon,

Joe

No comments:

Post a Comment