Jump to content

Spin Pac-Dizzy for Midway Pac-Man hardware


Recommended Posts

Hi everyone, if I have put this in the wrong please I apologise.


I thought I'd post this project here as I have a great appreciation for all the coders on AtariAge.


I enjoy writing code on arcade hardware, my experience is mainly with Midway Pac-Man hardware. This has a nice restricted environment ann I like attempting to do things that the hardware wasn't designed for (just like all the atari 2600 coders are doing).


Pac-Man basically is a Z80 based fixed tilemap system, rendering static 8x8 tiles from a bank of 256 stored in 4K ROM. It can also render 6 16x16 pixel sprites, again statically defined in a 4k ROM.


There is a small amount (you lot would call it large) of RAM around 900 bytes and 16K of ROM space.


I've completed a number of projects like sinewave scrollers and full screen scrolling


Sine wave scroller https://www.youtube.com/watch?v=4-o57DPCt8k


I've also finished a little game for my students to help with Assembly language called Ghost Hunt, this runs in the latest versions of HBMame. I have fully commented source code for this if any one wants a copy.


Ghost Hunt https://www.youtube.com/watch?v=bOm_Wk6xqDA


But my latest project, which I've tried to chronicle this last week as I built it is to attempt to produce a tribute to Paul Shirley's SpinDizzy game for the 8 bit machines, I'm calling it Spin Pac-Dizzy. I've done one major complicated part rendering the room data and below you can see the results in this playlist here.





I develop using VS2015 and SJASM, plus a load of support programs for building sprite roms, tilemap roms from graphics files as well as the usual data set creations.


Use Mame to do development coding before burning roms and installing them on my Pac-Man board.


Here are a couple of pictures from the code running in mame, please check out the videos for some background and commentary






If anyone has any questions please ask.







  • Like 5
Link to comment
Share on other sites

  • 3 months later...
Managed to find some coding time and been working on Spin Pac-Dizzy, trying to sort out the impulse and deceleration of the main character (which is tricky to balance).

I decided to take a break from that and work on the final version of the compound tile lookup system used during rendering.

Anyway got round to designing 3 data different structures to allow 3 different compound tile lookup methods. Remember there are no transparent tiles it's just a single layer of tiles, so I have to use compound tiles to give the illusion of drawing tiles on top of each other.

The original method just linear searched a linear array with 3 byte values at each location, this was never intended to be the final version, just wanted something simple to test the rest of the renderer (which was complicated enough).

The original method required 930 bytes of data and 58 bytes of code. There are 94 tiles that have compound tiles associated with them, the most and single tile has is 16 compound tiles (that is there are 16 different tiles that can be placed on top of it in a scene).

The compound routine lookup needs to find out if an existing tile on the screen has any corresponding compound tiles (tiles that give the illusion of two tiles sitting on top of each other). If there aren't then the new tile overlapping is just written to the screen. IF there are any we need to then find if our new tile has a compound relation, if it doesn't then the new tile is written, if it does then the compound tile is written.

This involves basically searching twice, once for the existing tile and again for the new tile. Unfortunately this has to be done for every object in a scene here's some simple maths about how many objects and tiles.

maximum objects in a scene is 7x7x8 = 392 objects

the number of tiles used to represent a standard half height cube is 12

So a room full of half height cubes (392), would require 4704 tile writes and hence 4704 searches of the compound tile data. This means this routine is crucial to the whole rendering process and needs to be optimised without wasting too much memory.

I came up with 3 different fast compound tile search methods, that required data being written in a specific way for each.

Method 1) binary tree index: 69 bytes of code and 1186 bytes of data

pointing to a linear array of tile pairs (new tile, compound tile), searched with a linear search

Each node in the tree takes 5 bytes:

Key byte: existing tile in tilemap we want to overwrite

compound pair array addr: where compound tiles for this tile existing

left offset byte: to move to the node hanging on the left branch

right offset byte: to move to the node hanging on the right branch

This tree takes up 470 bytes. It wasn't trivial to produce this data, which was a great exercise in itself. I had to binary search my linear data to create a tree structure, unfortunately the branch distances were larger than 255 bytes so I then had to breadth first search the tree to generate a node order that meant the offsets never got over 255 bytes, it then had to link up the tree in this depth ordered format. Like I say this was a wicked little coding exercise and even though I won't use this method going forward, it was cool doing it.

this uses a tree containing 470 bytes for the index, plus the linear pairs (shared between all 3 algorithms) of 620 bytes

Method 2) linear index: 85 bytes of code and 998 bytes of data

searched using a binary search, pointing to the same linear tile pair array

Has the tree is basically a binary searchable data structure I decided to try and lay the data out in a linear array and use the binary search technique on this.

The index needed 3 bytes per node:

Key byte: existing tile in tilemap we want to overwrite

compound pair array addr: where compound tiles for this tile existing

as this takes up 282 bytes it's just over the 255 limit for organising the top and bottom pointers, so a little jiggery pokery had to be performed, which made the code longer than I liked.

Binary search is a fantastic technique that allows you to discard half your data set every time you examine a single node, this makes it an ultra fast search method.

Method 3) index lookup table: 47 bytes of code and 1154 bytes of data (cheaper than the tree method !)

This is a memory waster, but it was worth a try anyway as it's the quickest method possible. As there are 219 different tiles that can be placed into a scene but only 94 that actually have compound tiles associated, there is gonna be some wastage. This cannot be a spare lookup table, so using this method 250 bytes are unused. I should be able to slot other fixed game data (as its in ROM) into these spare locations as some of them are in continuous blocks, so all is not lost.

So this system just consits of the 16 bit addresses of the compound tile pairs, it's a simple case of doubling the value of the existing tile looking for and adding this to the base of the lookup table, all very quick and pretty straightforward.

I spent some time writing code so that I could dynamically switch between the different compound lookup methods, so that I could test their effect on rendering, the results are interesting.

The lookup index manages to shave about 85% of the time taken by the original routine and is actually twice as quick on interesting scenes compared to the quick index search methods 1 and 2. It does use 7% of the available ROM I have, which coupled with the renderer takes it to around 12% of the total ROM.

I'm decided to go with that method, but if I have to I can see that the other search methods are pretty quick and could be used if I get desperate.

I'll record a video showing the rendering tomorrow and you'll be able to see the speed differences quite clearly as I unlocked the view rotation so it runs continuously.

Here's a spreadsheet of the data to look at and the two scenes being rendered.





Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...