Monday, August 15, 2011

LAST BUT NOT LEAST.... Ultima 1 revisited program clarifications...

HI Beth,

A few things...

1.  I tested the POKE and it worked like a charm!  My initial program had the row and column values set in the main assembly program, which didn't allow for modification.  So, my test was to set the ROW and COLUMN as set variables which were equal to $1E and $1F.  I then entered in my Basic program two lines that read:

10 POKE 30,10
15 POKE 31,11

I did these lines before the BLOAD of my main assembly program and it worked!

The main character shows up on the map in the location set by the poke statements!   I tested this with different values and the character started in different locations on the map.   I love it when things work like they are suppose to.  So now I think I can use a 2 dimension array in basic with X,Y to track the main characters movement and when the player wants to save the game I can PEEK these values and BSAVE them, right???   Also, I know that the first Page of memory is 256 byte locations, do you think I should use these bytes for all of my variables or is there a better location from memory to use??  So now that I know how to use the POKE statement in my basic program I was thinking that I could use these locations for the variable such as player character map location, hit points, gold, experience, food, monster and transportation locations, etc...  right???  Then I was also thinking I could save all these values with a BSAVE when the player wants to quit and save his place in the game.  Is this the correct way of doing this?

Joe, yes, that’s exactly how you pass information back and forth, as well as loading and saving the data. However, be VERY careful with using the “first page of memory”. That is referred to as “zero-page” memory and it’s a very valuable and constrained resource. Here’s a link to how it’s being used by the system:


You don’t want to use any locations that might be in use by something else, as those may change your values or you may corrupt what it is that they do. You should reserve your use of zero-page memory for critical timing routines where you optimize using fast instructions that rely on zero-page indirect addressing, for example. For all of your program variables, find a higher location in memory and use PEEK and POKE on those addresses. (This gets back to figuring out a memory map so you can know exactly where in memory you’ve allocated all your variables, your data, your programs, etc.)


2.  Concerning the towns and castles:  Since there are probably 8 to 10 castles and 30 to 40 towns, which all seem to look slightly different.  I was thinking I SHOULD do them in assembly to save space as you mentioned but I still have the issue of the number of shapes that will be created for all these places and how do I use data compression?  The world map was easier because I only had about 12 or so main tiles on the map, less than 15 total, but the town and castle have way more.  I won’t be able to use the data compression even if I create a separate assembly program for each separate town or castle because some of the towns look like they have more than 20 shapes that make up the tiles for the town!  So that bring me to the main question:  Should I just do them in assembly and use normal data strings which use a byte for each shape #, like I did in the beginning.  This way I could create one assembly program that would generate the images for all of the towns and castles  OR should I do them in BASIC, which would use a single file that had all the shapes necessary for all the castles and town and create a ransom assess files that would have a text file that used three values for each shape, such that it would have the X,Y, and shape # for each shape in each town/castle.    Which do you think would take up more space; the BASIC program of the Assembly program????  I know that space is a critical issue and I would hate to start spending a bunch of time of one path then realize I should have done it the other way just to save a bunch a memory!!!  

Well, I think you’re fine with doing it in Basic, but I don’t see why you need three bytes for each shape. Why not just store the data in data strings like you store uncompressed maps, so each byte is the tile # and the X,Y is implied by the location of the tile # in the array? You just lay out 20 x 10 tiles for 200 bytes, for example. You could still randomly access the file every 200 bytes or so to pick off the specific town/castle you wanted, or you could have a bunch of different little data files. Regardless of whether you use basic or assembly you should keep the X & Y out of the data, imho. Save that space at least! I don’t think you need to bother with compression, since you could load in the town/castle instead of an outside map when you switch between modes, for example.

3.  I think I got where you are coming from concerning monsters and transportation tiles and the memory they use but let me reiterate just to make sure.  Since I plan on using individual memory locations for the locations of transportation tiles and monster tiles, similar to how I did the ROW and COLUMN deal.  Did you mean I should set aside a number of these locations just for a set amount of these items locations on the map?  Meaning, if I use the first page of memory and set aside 10 or 15 for each transportation tiles, which would mean two byes needed for each tile, which is basically for the X and Y location values, correct?  This way I could create arrays for each new monster or transportation tiles and save their location in each byte with their X and Y values.  Then I would able to check these values on each character move and if they fall into the map screen parameters, I could use them to draw their location on the map.   Is this what you meant or am I way off???

Well, again, don’t use the first page of memory. Find another block somewhere for this type of data. I would argue you still need 3 bytes for each, one byte for the type of transportation (e.g. 1 = cart, 2 = horse, 3 = ship, etc.) and an X, Y for that as well. Otherwise yes, what you say sounds correct!

4.  Concerning front and back buffers:  I understand now what you mean about using these two pages of graphics and will start testing them.  I know now that I have to add Page 2 "$4000 and up" graphics memory locations right after my Page 1 graphics locations used for indirect indexing.   After that I will have to create another addition to my program to incorporate these two page swaps.  The question I have is:  You say to draw on screen two that is not seen by the user but how do I draw on the screen when I don't know which direction the player wants to go?  My understanding was I would start with the initial map view on Page 2, while Page 1 is blank!  Then show Page 2 and when the player makes a move I would draw on Page 1 then switch them.  Is this incorrect?  If so, I'm not sure how to implement the page flipping for the game.  I see there being a delay between page flips due to the amount of time it takes to get the new information concerning the direction move.  I also see how the 90% could make a huge difference with speed due to the page flip delay!!!  I need to figure out how to get the 90% shift working because I already notice that the redraw is not fast enough!!!  I will do more testing on the 90% map shift because I have to get this working in the program and then utilize page flipping at its most!

It’s easy for me to say, but don’t overthink this too much. It’s actually pretty simple.

1.       Get user input for direction they want to move
2.       Copy the 90% of the front buffer to the new location in the back buffer – shifted by user input
3.       Draw the remaining 10% of the back buffer required
4.       Flip the pages
5.       Goto 1

Since you aren’t trying for constant animation, you don’t have to keep things running. You can always wait for use input. If you were animating (say you wanted to have the water tiles always moving so it looked like all the waves were in motion) you wouldn’t wait for the user input at step 1, you’d just check to see if there was any.

To break this down further:

Step 2:
You can literally copy screen-memory lines from the front-buffer to the back buffer. You just need to copy them from the current location to the shifted location. So instead of copying from $2000 to $4000 directly, you might copy from $2000 down a full tile to $4080 or whatever it is in the event the user decided to move up.

Step 4:
Flipping the pages is very fast. All that happens here is you switch which hi-res screen the user is seeing. As I recall, this is done like so (where K can be 0 or 1):

POKE49236+K,0                               //set hi-res graphics page (K)

And to keep things consistent, you might want to follow it with this:

POKE230,32+(32*(K=0))                 //set hi-res plotting page (for basic, 32 = page 1, 64 = page 2)

And of course this clears the current plotting screen to black (if you need to do so)

CALL-3086                                       //clear current hi-res screen to black


5.  I had an idea that I wanted to get your opinion on:  I was thinking of using a main location array in the BASIC program that would have the main character map location tracked at all times.  This array would basically have the X,Y coordinates of the characters location on the world map.  My thinking was I could use this array values for a number of issues:

 A.  I could have all the town, castle and signpost X,Y locations on the world map saved in a data file and check after the player hits the ENTER key, which is the key used to enter these locations.  Once the enter key is hit I could check against the players X,Y position and if it matches an X,Y value within the database I would know exactly which town, castle, or signpost for that matter, which the player was trying to enter!!!  Then all I have to do is a simple CALL statement to the portion of the assembly program that draws that town or castle of updates the quest when the signpost is visited.  What do you think?? 

B.  Also this would work out great for when I want to board a transportation tile because when the player hit the "B" key for board I could check this value against the values save for all the purchased transportation tiles on the map!!  What do you think?

C.  Also, also... "hehe"   I what be able to use this X, Y value for the monsters to track too.  I know in the game that if you move on the map while a monster is near it will move after you.  So I thought that I could use this X,Y value to help the monster's track the player’s location and attack this location accordingly.  Again, what do you think?

All of the above sounds good! I worry a bit when you say “data file”. As long as you mean a data block in memory, cool. You don’t want to be loading an actual disk file every time the player hits ENTER, though! I’m assuming you meant in-memory locations.

Also, as a bit of an aside, check out this article:


I realize you’re not really concerned with how to do smooth animation on the Apple ][ (at least not yet), but this goes into that, which is a whole topic in and of itself. What I thought you might find immediately interesting was to check out how this program interfaces with its assembly bits. It involves a fairly integrated Basic and Assembly program which both read/write data used by the other, with calls from the Basic program to the Assembly program(s). Sound familiar? Check out how they made it work and maybe it will help further inform your own efforts!



I know these are a lot of questions but what better way then to go to the source!!!

Thanks again,

Joe

MORE, MORE CONT.... program changes and updates...

Hi Beth,

You are right, there is a space part to the game where you travel in a space ship and have to doc to a space station. Then you enter hyperspace with one of two or three types of ships to get to the wizard. This doesn't look too complicated but I will leave that for last.
I was able to create one of the towns in assembly just to see if I could do it but I don’t think it will be practical. I have a question regarding the towns and castles: Q. On map one, "There are 4 total maps in the game!" there are 8 towns and 2 castles and they all look different! If I keep this numbering throughout that would make 24 towns and 8 castles! I think they are all different but I'm not sure because I have been able to take a look at each one. The problem I see with using assembly is if I use the same data compression method as in the world map I will have a problem with needing more shapes then 15! I think because of this issue it does seem to be more practical to make the towns and castles in basic using a character generator and maybe text files. What do you think?
Would basic be more data on the disk then assembly?
This make sense when you talk about page flipping because then I would be using the low res graphics screen and the HGR2 screen would be available to me for page flipping. I still am a little vague on this page flipping process.   So to understand what you are saying: 
1. Show user front-buffer graphics screen -  “I awesome this is the main world map screen?”
2. Draw all terrain on back-buffer graphics screen – “What is back buffer graphics?”
3. Draw transportation at locations on back-buffer – “again, What is back buffer?”
4. Draw monsters at locations on back-buffer
5. Draw player in center tile of back-buffer
6. Switch user to be looking at back-buffer. Back-buffer is now front-buffer. Front is now back.
7. Goto 2.
Is the back buffer page 1 and front buffer page 2 graphics screens?
Also, if I am going to pass data back and forth from basic to assembly using POKE and PEEKs, Does this mean for example:  Let’s say I’m using X and Y for grid coordinates on the map and I need to have the character start at x=60, y= 35.  I get the impression that I would use the first page of memory like $1E and $1F for values stored in the game.  So if I set the following variables in my code would this be correct:
Row                 equ      $1E
Column            equ      $1F
Then in basic I could POKE the value 60 into $1E and 35 into $1F before I do the CALL statement and the main character would be all ready to start at a new location on the map correct?
This seems logical.
Thanks
Joe

+++++++++++++++++++++++++++++++++++++++++++++++++++

Hi Joe,

I think you have a lot more flexibility in how you handle the towns/castles. You’ve sketched out one idea, using the character generator and text files. I think that’s totally reasonable. You could load each one individually as needed.

The data itself won’t be any bigger. However, Basic is a big fat pig. It takes up space just to load the text that makes up the Basic. It takes up memory and CPU overhead to run the Basic interpreter. So from that perspective, you will take up more space on the disc and in memory using Basic. Hopefully that won’t be a problem! I don’t think it should be, it just comes down to how you structure things and that’s on you.

As to terminology, “front-buffer” and “back-buffer” are video pages 1 and 2. However, whichever one the user is currently seeing is always the front buffer. The other one (the one you always draw on) is the back buffer. So front and back alternate between pages 1 and 2. I’ll lay it out explicitly:

Game Frame 0 Render cycle: 
Front buffer – Visible to user – Screen 1 - black screen
Back buffer  - Not visible to user – Screen 2 – drawing Game Frame 0

Game Frame 1 Render cycle:
*flip frames*
Front buffer – visible to user – Screen 2 – has Game Frame 0 on it
Back buffer – not visible to user – Screen 1 – drawing Game Frame 1

Game Frame 2 Render cycle:
*flip frames*
Front buffer – Visible to user – Screen 1 – has game Frame 1 on it
Back Buffer – not visible to user – Screen 2 – drawing Game Frame 2

Etc.

As far as the Peek/Poke thing goes, you’re absolutely right. I’m not sure what address you want to use for your values (that’s up to you), but you have the right idea for communicating between the two.

-          Beth

MORE CONT.... program changes and updates...

Hi Beth,

I guess I'm confused...   I thought that I would use the Page2 graphics screen for the towns and castles!?   The reason I thought this was because if you went to page 2 for a town, when you left the town you could go right back to page 1 and nothing would have changed and you wouldn't have to draw or shift anything to get the same location on the map that the character was on before he went to the town or castle.  Is this wrong? 

This brings me to the issue of the towns and castles... I'm having a hard time trying to figure out how I should do the towns/castles.  Do I program these in assembly also and make either individual Bsaves for each town/castle or one big file for all the towns and one big file for all the castles?    OR, should I do the towns/castles in Basic using generated character sets that have the town/castle graphics, which would replace the lower case character set.  "These characters aren't used in the game and could be redrawn for town and castle graphics. 

Any idea what the best way to go regarding the towns/castles? 

I think I understand your information below regarding the monsters and transportation devices but I will need to test it out and will I still be able to do this if I plan on using page 2 graphics screen for towns and castles?

Which part of the game do you think uses actual basic coding?  I don't think he programmed the entire game of Ulima 1 in assembly since he didn't know how to program in assembly till Ultima 2 or 3.  His friend Ken Arnold was an assembly programmer who did the tile map part of the game but I think the map and the dungeons are the only part that was programmed in assembly.  Not sure though!

The hard part of this for me is I'm trying reverse engineering the game and figuring out which parts of the game are in assembly or basic and I have no idea which would have worked the best.  I know speed is the biggest consideration but menus, town, and castle movement doesn't have speed issues.  I'm feeling as if I'm getting lost in the minutia......

What do you think?

Thanks

Joe

+++++++++++++++++++++++++++++++++++++++++++++++++++

Joe,

Hey there! No worries. Like you noted earlier, there are a lot of ways to accomplish any given programming task. As long as it works at the end of the day, it’s all good.

However, I think there’s no reason to have one page for exterior and one for interior. You could easily manage the transition out of a town by simply doing the global-redraw thing on the back-buffer and then showing that and resuming a normal page-flipping scenario. Personally, if I were implementing, I’d have the page-flipping thing using both video pages for outside to keep everything simple and then I’d use one of the two pages for the town. When it was time to leave town, I’d just launch the “outdoor app” and go back to page-flipping.

If you aren’t page flipping you’re going to have to make your code significantly non-optimal, in that you have to do the monster/transport array lookup for every tile you draw. That will blow the whole reason you did all that assembly work in the first place, imho. Alternatively, you can always draw the monsters/transport afterwards but you’ll end up with a nasty refresh flicker.

As to how to implement the town/castle, they’re pretty easy to do in Basic and with the generated character sets, you might as well go there! As you note, there’s no speed issue there. You’ll just have to figure out the best way to transition your drawing algorithm and your data storage between the two modes. In a way, it’s like two totally different games. You might even try to handle it that way – run the towns/castles in one program (basic) and then launch an “outdoor” program with your assembly when you go outside, and vice-versa. Keep the problem separated until you know what bits you need to optimize and constantly keep in memory (e.g. player statistics).

I’m sure he did the town/castle in basic. I’d also bet he did the dungeons in basic as well. There’s really at least three programs here – outside (assembly), dungeon and town/castle. Also, was there a shooter/spaceflight thing in Ultima 1 or am I remembering wrong? I know Ultima 2 went into space, but for some reason I’ve got this screen memory of manipulating a little spaceship around in Ultima 1 and going “pew pew pew”. Maybe I’m crossing old games. Anyway, if present, that would make 4 programs…

-          Beth

CONT.... program changes and updates...

Hi Beth,

Hey, take a look at this new video that covers the movement of all the different transportation tiles.


The game is coming along but this movement test brought up a difficult problem I'm having. As you can see in the video I've been able to work out the movement and collisions of all the different types of player tiles. The one problem that came up is this:
Q: How do I place a transportation tile that is purchased on the screen and keep track of it when I move around the map and they tend to stay in location they were left last? Since I'm using this special data compression for the map tiles I don't have any idea how to place a ship for example on the map and be able to keep track of it when I move away from it. I need to be able to keep some sort of data record of all the different types of tiles like a horse or a cart or a ship and if don't board the tile I need to know exactly where it is if I move away from it and move back to it later. If a ship is left by a castle and I move to another world map should I use some array in basic to keep track of it? I was thinking that every time a purchase is made of one of the transportation tiles I could create a data files and enter that tiles as an array with an X,Y location. If the entire world map section is 180x80 and if the ship gets place near the castle then that would be for example 120x45 as a coordinate. I kind of understand how this may work but since I'm using this strange data compression format for the tiles I'm not sure how to make it so the ship will appear when it is close to the edge of the map. Am I explaining this right?
Q: I also see a problem if there are multiple purchases of a bunch of horses, ships, and other items that need to be tracked all the time so they show up when a character is near them on the map. What would the best way to do this: Assembly or Basic? In basic I can use an array and a write to a database file. In assembly I'm not sure without creating a bunch of unnecessary code!
Q: This also brings up monsters; they are going to be on the screen at different times and they also need the same type of tracking as transportation tiles. The problem with this is they move where the transportation tile don't! Do you have any ideas on how to cover either one of these ideas?
Thanks
Joe

++++++++++++++++++++++++++++++++++++++++++++++++++

Hi Joe,

Nice to see how smooth the graphics are turning out! So, one important question for you – are you utilizing page-flipping to draw your graphics? Because 1) you should be and 2) it will simplify the answer to your questions.

Basically, you show the user either page one or page two of the graphics while modifying the other page where they can’t see it. When you are done modifying it, you flip the pages, show the user the one that was hidden and resume the process. To quote from Wikipedia:

“The Apple II Hi-Res graphics mode did have one crucial advantage over IBM's CGA. Just as there are two text screen pages (and two Lo-Res graphics pages), so there are also two Hi-Res pages, mapped one right after the other in memory. (The second Hi-Res screen was mapped to 0x4000-0x5FFF, or 16384-24575 in decimal.) The CGA, on the other hand, supported only one graphics page at a time. Not until the EGA video card was released could the IBM platform support multiple pages of graphics simultaneously. Naturally, this simplified animation on the Apple II. A programmer could display one page while altering the other (hidden) page.”

Why is this important? Because your algorithm can look like this:

1.       Show user front-buffer graphics screen
2.       Draw all terrain on back-buffer graphics screen
3.       Draw transportation at locations on back-buffer
4.       Draw monsters at locations on back-buffer
5.       Draw player in center tile of back-buffer
6.       Switch user to be looking at back-buffer. Back-buffer is now front-buffer. Front is now back.
7.       Goto 2.

Do you need to keep a data file? Does it really need to be infinitely long? Couldn’t you just allocate say 10 or 100 entries for the x,y coordinate of the transportation type? 100 entries, 1 byte for type, 1 byte for x, 1 byte for y? So, 300 bytes? Do the same for monsters, provide perhaps 100 entries, for another 300 bytes somewhere. Make it so 0x00 for type is “none”. When the player buys transport or a monster appears, you scan through the array and replace the first 0x00 entry. When a monster is destroyed or transport disappears, you put 0x00 back in that array entry.

Then what you need to know is what the view coordinates are for the screen. So, for example, let’s say your screen is from 10,10 to 30, 20.  During step 3 in the above algorithm we would then loop through all 100 entries in the transportation list. For any non-zero type, you compare to see if the x coordinate is between 10 and 30 and if the y coordinate is between 10 and 20. If so, you draw it.

For step 4, you loop through the monster array the same way.

This nicely keeps your world-drawing/compression system separated from the update redraw of monsters/transport.

Sound reasonable?

-          Beth

Some information clarification concerning new changes to the program...

Hello all,

Well I've been doing some research and asking a lot of questions hoping to find a way to incorporate new changes to the program.  These changes cover inserting transportation tiles, transfering data back and forth from Basic to assembly, tracking movement from assembly within Basic, and being able to save data from the assembly program while in BASIC.

I've been conversing with Beth and the next few blog will show what has transpired through email between Beth and myself.

Enjoy...
____________________________________________________________________

Hi Beth,

I wanted to give you a update on what I've been doing and how the program works so far.
A short time ago I told you that I figured out the movement part for the game and it was a lot faster than before. Here is the YouTube link to the video I made for the second movement test.  It’s pretty cool!!!!!


As you can see it is faster than before but I know I can make it faster if I can only figure out the memory shift part of the code. I have an idea but I need to really sit and think about it to get it right.

The assembly code for this video works as follows:
1.  I have a subroutine that initializes the graphics on the screen and clears it to black, leaving the four text lines on the bottom.
2. The next subroutine initializes all the variables and the row and column values for where I want the upper left corner of the screen to start.
3. I setup data string names for the tile reference values that correspond to each map line, such as, MAP1, MAP2, etc...  These hold the tile values such as 3 for trees, 4 for plains, 9 for mountains, etc..  These are all set in a serial fashion with one tile reference after the other.  Since the map is 180 tiles wide I had to setup each tiles value one after the other till I had all 180 tiles referenced in each data MAP line.
4. Now I run a subroutine that reads down to the row value, which I start at MAP7, and then it read to a column value, which is a 10. This gets me the starting upper left corner tile reference point.
5.  Now I run a subroutine that loops the first 20 tile values in the data string and places them in a MAPSTORE array.  It then drops down to the next MAP data string and reads the next 20 tiles values and adds them to the array.  When all 200 tiles are in the array I run the next subroutine to add the center character tile, which I do by replacing the 105 tile with the shape reference of the troll.
6.  Next, I loop through each tile from 0 to 199 and setup the shape data for that individual tile. So I create two 160 byte arrays called TEMP and TEMP1.  These two arrays hold the data for the 10 tiles that go from top to bottom, starting on the left side of the screen.  They are 160 byte because they represent each graphic line from the top of the screen to the bottom of the screen.  This leave the lower portion of the screen for the 4 text lines.  Also I use two temp arrays because this lets me draw both A and B bytes of the tiles at one time instead of just the 1 byte at a time.
7.  Now I draw the first 10 tiles on the screen and when they are complete I read the next 10 tiles into the TEMP arrays and draw them next.  I loop this for the 20 tiles across the screen.
8.  Once all the tiles are drawn I have four subroutines that are used for the movement of UP, DOWN, LEFT, and RIGHT.  These are called from a basic program using their memory location with a CALL statement.
9. The movement is just incrementing or decrementing the ROW or COLUMN value and running through the initial subroutines for the read and setup parts.  I know I have it redrawing all 200 tiles again from scratch but I haven’t figured out how to do the 90% yet, which I know will be faster.  Within these subroutines I also do a comparison check for the mountain tiles and the ocean tiles to make sure I can’t walk through them!
This is a very quick and dirty write up of the process and I probably could code the game cleaner but I know you get the idea.  If you have any input as to the process I’m using and can think of anything that would make it faster or cleaner.
If was funny, because I had just figured out how to move around the screen after a LOT of trial and error programming and boy was I on cloud nine! You cannot believe how frustrating it is to change your program, wait 10 minutes to compile it, and then make changes to the basic program to call the correct memory location for the movement keys, and BAM… the program shows scattered tiles all over the screen! As you can imagine this is a very slow and grueling process!   Once I thought I was ready to start entering in all the data lines for the world map, I realized this was going to take up a lot of space!  I had to use a single byte for each tile reference, which as you said is a huge waste of space!!!  So due to this process I was having to enter line after line of data strings each map line starting with all ocean tiles on the top of the screen and going down map line by map line 20 data bytes per data string.  The entire map is made up of 4 main maps that are side by side and 180 tiles wide give or take a few ocean tiles.  Still on my programming HIGH from finally figuring out to movement process, I only got down to about the 24th MAP data line and it gives me a memory space error.  CRAP!  I can’t believe my eyes!  I’m thinking to myself, “yeah, I figured it out and now all I have to do is enter all the map data and test is out!”  WRONG!  I was still 60 lines away from just getting the entire map data entered!
So that brings me to the point I’m at right now which is reprogramming a big part of my code to be able to now read compressed data strings!  I think I understand how to do it and I’ve been testing some new code.  I know I need to use the ASL and RLS functions.  I also read that you can do each 4 times to get the 4 bit shift!
I want to thank you again for your wisdom and advice!  I like how you give me just the right information to get me going in the right direction yet you don’t just give me the code.  This works out great because your email updated are like puzzles that I need to figure out and I am learning more about programming assembly when I have to sit down and really think about what the program is doing and what I need to do to get it to work correctly.
God bless you!  You are an incredible help and I just hope you stick it out with me because I am going to have more questions as I overcome each breakthrough and move on to the next section of the game.
I will let you know when I figure out the new code to read the compressed data strings.  I’m close, very close and the amazing part is I think I really understand how to program in assembly language.  I’m able to code right on the screen and see in my head what the program should do once it is assembled.   Sometimes it does wacky things but more and more it does exactly what I thought it would do!  This is awesome!
Thanks again,
Joe
+++++++++++++++++++++++++++++++++++++++

Joe,

Nice video! It’s pretty cool to see the game running like that, brings back memories for me! J

And I’m glad I’ve been able to point you in the right directions to figure things out. It’s super-satisfying to crack your head against something, finally have the lightbulb go off and then see the results of your understanding, isn’t it? There are things I love about programming!

One of the great thing about the Apple 2 is just how accessible and understandable it all really is. And all of the concepts learned there are still tremendously relevant in programming today. I often feel bad when mentoring kids coming out of school, that have no idea of what bits really are. They don’t understand having to keep track of memory, limited resources, how to optimize or solve these types of puzzles. They have to learn that stuff on the job, and it’s hard to do. Having learned it in the trenches on an Apple…well…there’s not really a better learning environment, imho.

Another thought I’ll leave you with – optimization. It’s something you’re obviously thinking about. Compression is a form of size optimization. Making the screen draw faster is a form of speed optimization. Usually you can optimize for size or speed, but not both. Then there are algorithmic optimizations – like the 90% thing. That’s a high-level, write a different, faster approach to solve the entire problem. Those are always worth doing before trying anything else.

However, eventually you’ll get to the point where you’ve optimized for speed vs. size as best you can, and you’re working with the best algorithm you can. At that point if you want it faster, you’ll have to start counting cycles. I’m only saying this to put it in the back of your head, for your awareness. You may never need to go there on this project, but it would be educational for you to do it at some point with at least a little chunk of code. What I mean by counting cycles is you take your tight loops of assembly and figure out how many clock cycles that loop takes to execute. You can look that up, each opCode has a fixed cost.


So, looking there I see things like this:

LSR (Logical Shift Right)

Affects Flags: S Z C
MODE           SYNTAX       HEX LEN TIM
Accumulator   LSR A         $4A  1   2
Zero Page     LSR $44       $46  2   5
Zero Page,X   LSR $44,X     $56  2   6
Absolute      LSR $4400     $4E  3   6
Absolute,X    LSR $4400,X   $5E  3   7

See how shifting left on the Accumulator is WAY faster (TIM) than doing it anywhere else? Good to consider when writing that algorithm.

A quick example: how long does it take to divide by 16 (right shift 4 times) vs. dividing by 10? I am using this example since you asked about it earlier in regard to the compression algorithm. Well, you count up the opCodes. That LSR will take 4x2 = 8 cycles. Pretty good. However…there’s no way to divide in 6502. You have to write a program to do it. I looked one up:

A SIMPLE DIVISION PROGRAM

10 ;
20 ;DIVISION.SRC 
30 ;
40  *=$0600 
50 ;
60 DVDL=$C0 ;LOW PART OF DIVIDEND
70 DVDH=$C1 ;HIGH PART OF DIVIDEND 
80 QUOT=$C2 ;QUOTIENT
90 DIVS=$C3 DIVISOR
100 RMDR=$C4 ;REMAINDER 
110 ;
120  LDA #$1C ;JUST A SAMPLE VALUE 
130  STA DVDL
140  LDA #$02 ;THE DIVIDEND IS NOW $021C 
150  STA DVDH
160  LDA #$05 ;ANOTHER SAMPLE VALUE 
170  STA DIVS ;WE'RE DIVIDING BY 5
180  ;
190  LDA DVDH ;ACCUMULATOR WILL HOLD DVDH 
200  LDX #08 ;FOR AN 8-BIT DIVISOR 
210  SEC 
220  SBC DIVS 
230 DLOOP PHP ;THE LOOP THAT DIVIDES 
240  ROL QUOT 
250  ASL DVDL 
260  ROL A 
270  PLP 
280  BCC ADOIT 
290  SBC DIVS 
300  JMP NEXT 
310 ADDIT ADC DIVS 
320 NEXT DEX 
330  BNE DLOOP 
340  BCS FINI 
350  ADC DIVS 
360  CLC 
370 FINI ROL QUOT 
380 STA RMDR 
390 RTS ;ENDIT

Okay…So I’m not even going to try to add up the cycles there. Maybe 100 to divide by 10? Division & Multiplication are both VERY expensive on the 6502, so it’s always best to work with shifts and base 16 (that’s an important lesson right there!).

Anyway, to pedantically finish out my original thought on optimizing – so the first divide by 16 takes 8 cycles, the divide by 10 takes 100. Then consider that you’re in a loop, where you are going to do that shift or divide to uncompress 10 full rows (or 1800 tiles). That’s 14400 cycles vs. 180000 cycles. Let’s say you’re shooting for 5 frames per second. That’s 72k cycles/sec of cost vs. 900k cycles/sec. And a 6502 can only do about 500k cycles/second! So right there you can see the difference that little optimization makes in what you can actually do – and you can directly quantify it to real performance gains.

All of this is to say – once you have a good high-level algorithm working, figure out where you can speed up loops, copies, divides, shifts and other places that are done many times per second. And figure out the cost the way you currently have it implemented vs. what you are planning on changing it to. You may find the tradeoff not worth your time to implement – or you may even discover your cool new way of doing something will actually be slower in total cycles!

Anyway, best wishes and keep it rolling, it’s great to see it coming together!

-          Beth

Sunday, August 7, 2011

Ultima 1 revisitied movement test #3 - transportation modes w/ collision


Video #3 Different types of transportation movement modes and collision testing
In this third video installment I'm testing all six different types of transportation modes within the game. This movement test consists of the following modes:
1. Horse
2. Ship
3. Raft
4. Cart
5. Land Speeder
6. Main Character

I have set each mode to a number key, which corresponds with the number next to the type of tiles shown. Example: If I hit the number 1 you will see a horse pop up... If I hit a #3 you will see a raft tile and so on...
Once the transportation tile is on the screen the movement and collision aspects will be consistent with that type of tile. Each tile has a different collision characteristic which is as follows: The ship and raft only move on the ocean tiles. The Land Speeder can move on any tile except the mountain tile. And finally the Horse, Cart, and Main Character can move on any tile except the mountain and ocean tiles.
This movement test also shows a portion of Map #4, which is the last of the four maps. In the game you can travel left to right through all four maps but if you move up or down from a map you will cross to another map #1 altogether. I need to figure out which map routes are setup and have them checked in the game subroutine.
So far I have all four map created in an excel doc and will have them place in the 2 separate subroutine databases.
I will be testing the movement through all four maps soon and will post that video also when it is complete.
Hope you enjoyed this video because there are move to come.
Talk soon,
Joe

Friday, August 5, 2011

NEW TRANSPORTATION TILE MOVEMENT TESTING!









Hello all,
As you all know I’ve been working extensively on the movement part of the game and I realized that there is more than just one character that moves around the map. In Ultima 1 you have the following travel tiles:
1. Frigate
2. Raft
3. Land Speeder - WTF?
4. Horse
5. Cart
6. The main character!

UPDATE:  I've found that each of the transportation tiles have a set host of collision tiles they are unable to travel through.  Here are the following tiles per transportation mode:

The Frigate:  The Frigate can only travel over Ocean tiles and is restricked from traveling on any other tiles.

The Raft:  The raft also can only travel over Ocean tiles and is restricked from traveling on any other tiles. 

The Horse:  The horse can travel over any tiles except Mountains and Oceans.

The Cart:  The cart travels exactly as the horse!

The Land Speeder:  The land speeder can travel over any tiles except Mountains and Trees!


So with all these different modes of transportation I had to create the new shapes for each one. I’m testing a subroutine that will swap between all 6 shapes and move around the map with each one. One of the issues that needs to be resolved is different transport modes are restricted by different types of terrain. The Frigate and Raft can only travel over ocean tiles and must have a collision check against all other types of tiles, minus the main character tile and possibly a dungeon tiles out in the ocean. The Horse, Cart, and main character can only travel over normal terrain, minus Mountains and Oceans. Then you have the land speeder, which can travel over everything except mountains! So as I see it I can implement one main subroutine that covers all types of transportation modes, plus a subroutine that will swap out the different types of tiles on the maps. The big issue I see coming up is how to maintain these transportation items on the screen when they are not being used! In the game you can buy more than one of each of these items and once they are on the map the will stay on the map unless moved or sold. This causes a dilemma in that I’m not sure if I will be using BASIC or Assembly to keep track of these items. This is a looking like a deep puzzle because they won’t be a part of the initial database but will need to be placed on the map in multiple locations with what will probably be and DIM array to keep track of the x,y placement value. So, let’s say the map is 165x80 and I buy a ship and it gets placed at 120,30. This value needs to be maintained in some variable and be checked to make sure that when the map redraw happens and the ship is at a location that is referenced on the map, it must be drawn!
This is tough with the way I setup the compression part of my map database.
The good news is that I did figure out the movement for the different types of transport tiles and there collision properties. I will be uploading a video showing the new movement characteristics with the new tiles.
Just wanted to give you a heads up on where I’m at.

Talk soon,

Joe