[er1c1996]

EDIT: Here's a video of my own progress, do these addresses look right?

Hey all,

I've recently started to delve into the world of ROM hacks and scripting. My most recent project involves porting an amazing Lua NEAT (Neuroevolution of augmenting topologies) script for Super Mario World (via Bizhawk emulator), made by SethBling on Youtube. His script uses random inputs plus evolution via rightwards progress to "teach" itself how to play video games. Here is a video sampling his program.

Anyways, I've decided I wanted to port it to work on Sonic the Hedgehog 1. Now, I've considered its limited scope: it won't work on levels like Marble Zone or Labyrinth Zone, it may have trouble on loops, etc. But I kind of wanted to make this script as a proof of concept to play around with the idea of NEAT evolution.

Long story short, I've gotten most functions working, except the "getTile" function. What this function does is update the mini map in the top left corner (see the video.) It is contained in a loop which pass it the relative coordinates to the player that the map is currently updating, and it does so in increments of 16 to create 16x16 "estimates" of the tiles on the map. The problem is, I'm having some trouble understanding the RAM documentation for Sonic 1 and understanding how to obtain the solidity for a tile (I just need to obtain the "SS" flag in the 16x16 tile since the map is just a very rough approximation).

Can someone help a noob out by explaining how, given a set of coordinates, one can determine if there's a solid tile there? I can post the script if it helps.

Thanks!

This post has been edited by er1c1996: 07 July 2015 - 07:23 AM

[MarkeyJester]

So, I wasn't able to view that video in a high enough quality to see the values (my connection isn't very solid at times), I will tell you what I know though...

You'll start with the layout which is decompressed and loaded to RAM A400+, and every 40 bytes represents a line of chunks, this means:

• A400 - A43F = Top line of FG chunks from left to right.
  
• A440 - A47F = Top line of BG chunks from left to right.
  
• A480 - A4BF = Second line of FG chunks from left to right.
  
• A4C0 - A4FF = Second line of BG chunks from left to right.
  
• A500 - A53F = Third line of FG chunks from left to right.
  
• etc, etc...

Each byte in these lines is a single "chunk" (a square section displaying 256x256 pixels), the byte references the chunk table stored in RAM at 0000+, when reading the byte from the layout:

• 01 = Chunk 01 (RAM 0000 - 01FF)
  
• 02 = Chunk 02 (RAM 0200 - 03FF)
  
• 03 = Chunk 03 (RAM 0400 - 05FF)
  
• etc, etc...

Please note; 00 automatically places a "blank" chunk (empty and transparent). The chunks consist of words in a grid, each word is a single "block" (a square section displaying 16x16 pixels inside the 256x256 square), the words referrence blocks, this means:

• 000 - 01F (10 words) = Top line of blocks in the chunk
  
• 020 - 03F (10 words) = Second line of blocks in the chunk
  
• 040 - 05F (10 words) = Third line of blocks in the chunk
  
• etc, etc...

The words from these chunks are setup in the following format (Binary): 0SSY X0BB BBBB BBBB

• SS = Solidity "status" of block (00 = No solid | 01 = Top solid | 10 = Left, Right & Bottom Solid | 11 = All solid) - This is not the solidity itself, but rather a state control.
  
• Y = Block flip vertically (0 = No | 1 = Yes) - Note, these flip/mirror flags effect the solidity shape's flip/mirror
  
• X = Block mirror horizontally (0 = No | 1 = Yes)
  
• BBBBBBBBBB = Block reference ID

The block reference ID can only be from 000 to 3FF. This references from the block table at RAM B000+:

• 000 = Block 000 (4 words - RAM B000 - B007)
  
• 001 = Block 001 (4 words - RAM B008 - B00F)
  
• 002 = Block 002 (4 words - RAM B010 - B017)
  
• etc, etc...

^ the block table is useless for collision, it's for displaying tile patterns. But the block reference ID can also reference from a collision table. The collision tables are uncompressed but stored in ROM, here is the table offset in ROM of a Rev00 Sonic The Hedgehog game:

• ROM 004100 = Green Hill Zone long-word collision table pointer
  
• ROM 004104 = Labyrinth Zone long-word collision table pointer
  
• ROM 004108 = Marble Zone long-word collision table pointer
  
• ROM 00410C = Starlight Zone Zone long-word collision table pointer
  
• etc, etc... (In order of level ID)

The pointers will point to a table of collision IDs, for example, Green Hill Zone's pointer is "00 06 4A 00" (ROM offset 064A00), at that offset we have:

00 FF 1A 00 00 00 1A 00 1D 1C FF FF 09 14 0B 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF .... etc

Using the block ID, you can collect the correct collision ID. If the block ID is 006, you collect the 006th byte from the collision table, which is 1A. The collision ID is then referrenced from a collision and/or angle array, these can be found at:

• 062900 - 0629FF = Angle reference table
  
• 062A00 - 0639FF = Collision array normal
  
• 063A00 - 0649FF = Collision array rotated (for 90 degree collision with loops and sharp curvers/walls)

Using the collision ID we collected, we can reference the correct angle the block is using (062900 + Collision ID = offset of the block's angle ID). We can also reference the collision array. To brief aside about the collision array, this is a series of values that represent a soldity shape that the block has, be it a curve of some kind, or just a flat solid surface. Each collision block is 10 bytes big, this means:

• Collision ID 00 = 062A00 - 062A0F (Collision block 00)
  
• Collision ID 01 = 062A10 - 062A1F (Collision block 01)
  
• Collision ID 02 = 062A20 - 062A2F (Collision block 02)
  
• Collision ID 03 = 062A20 - 062A2F (Collision block 03)
  
• etc, etc...

Each byte of the collision block is a solid height from left to right of the block, for example: 00 00 00 00 00 00 00 01 02 03 04 06 07 08 0A 0B will give you:


If the number is positive from 00 to 0F, the solid starts from the bottom and rises to the top (for floor pieces).
If the number is negative from FF to F1, the solid starts from the top and drops to the bottom (for ceiling pieces).

The exact same method is used for the rotated collision, except, the numbers would be from left to right, and right to left (depending on positive or negative): 00 00 00 00 00 01 02 02 03 04 05 05 06 07 08 09


It is extraordinarily complicated, and one thing to explain, yet another to understand. The design (in my opinion) is the work of pure genius, and when understood, you can begin to appreciate the efforts that went into constructing a format, that provides a nice balance between speed and memory usage. For large level construction it is the most ideal.

For more information about the format, see this page: http://info.sonicret...g/Level_Editing

[flamewing]

Out of curiosity, what will you be passing as inputs for the AI? The solidity bits of each 16x16 or also the 16x16 ID and maybe solidity data?

[er1c1996]

flamewing, on 08 July 2015 - 03:38 PM, said:

Out of curiosity, what will you be passing as inputs for the AI? The solidity bits of each 16x16 or also the 16x16 ID and maybe solidity data?

Well, the way that SethBling made the script (which was based on the RAM of Super Mario World), the map gets updated via checking the tile at a specific co-ordinate, and then returning a 1 or a 0 based on a specific test at an address that isn't well documented in the RAM for that game.

I deduced that it is checking if the tile exists in some manner, and I figured based on my knowledge of the RAM of Sonic 1, that the solidity would be the quickest thing to check to confirm this (as non-solid tiles would probably not be useful anyways). Of course, I could check the tile's ID as well, but that requires a little bit more work.

[er1c1996]

MarkeyJester, on 08 July 2015 - 09:44 AM, said:

So, I wasn't able to view that video in a high enough quality to see the values (my connection isn't very solid at times), I will tell you what I know though...

You'll start with the layout which is decompressed and loaded to RAM A400+, and every 40 bytes represents a line of chunks, this means:

• A400 - A43F = Top line of FG chunks from left to right.
  
• A440 - A47F = Top line of BG chunks from left to right.
  
• A480 - A4BF = Second line of FG chunks from left to right.
  
• A4C0 - A4FF = Second line of BG chunks from left to right.
  
• A500 - A53F = Third line of FG chunks from left to right.
  
• etc, etc...

Each byte in these lines is a single "chunk" (a square section displaying 256x256 pixels), the byte references the chunk table stored in RAM at 0000+, when reading the byte from the layout:

• 01 = Chunk 01 (RAM 0000 - 01FF)
  
• 02 = Chunk 02 (RAM 0200 - 03FF)
  
• 03 = Chunk 03 (RAM 0400 - 05FF)
  
• etc, etc...

Please note; 00 automatically places a "blank" chunk (empty and transparent). The chunks consist of words in a grid, each word is a single "block" (a square section displaying 16x16 pixels inside the 256x256 square), the words referrence blocks, this means:

• 000 - 01F (10 words) = Top line of blocks in the chunk
  
• 020 - 03F (10 words) = Second line of blocks in the chunk
  
• 040 - 05F (10 words) = Third line of blocks in the chunk
  
• etc, etc...

The words from these chunks are setup in the following format (Binary): 0SSY X0BB BBBB BBBB

• SS = Solidity "status" of block (00 = No solid | 01 = Top solid | 10 = Left, Right & Bottom Solid | 11 = All solid) - This is not the solidity itself, but rather a state control.
  
• Y = Block flip vertically (0 = No | 1 = Yes) - Note, these flip/mirror flags effect the solidity shape's flip/mirror
  
• X = Block mirror horizontally (0 = No | 1 = Yes)
  
• BBBBBBBBBB = Block reference ID

The block reference ID can only be from 000 to 3FF. This references from the block table at RAM B000+:

• 000 = Block 000 (4 words - RAM B000 - B007)
  
• 001 = Block 001 (4 words - RAM B008 - B00F)
  
• 002 = Block 002 (4 words - RAM B010 - B017)
  
• etc, etc...

^ the block table is useless for collision, it's for displaying tile patterns. But the block reference ID can also reference from a collision table. The collision tables are uncompressed but stored in ROM, here is the table offset in ROM of a Rev00 Sonic The Hedgehog game:

• ROM 004100 = Green Hill Zone long-word collision table pointer
  
• ROM 004104 = Labyrinth Zone long-word collision table pointer
  
• ROM 004108 = Marble Zone long-word collision table pointer
  
• ROM 00410C = Starlight Zone Zone long-word collision table pointer
  
• etc, etc... (In order of level ID)

The pointers will point to a table of collision IDs, for example, Green Hill Zone's pointer is "00 06 4A 00" (ROM offset 064A00), at that offset we have:

00 FF 1A 00 00 00 1A 00 1D 1C FF FF 09 14 0B 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF .... etc

Using the block ID, you can collect the correct collision ID. If the block ID is 006, you collect the 006th byte from the collision table, which is 1A. The collision ID is then referrenced from a collision and/or angle array, these can be found at:

• 062900 - 0629FF = Angle reference table
  
• 062A00 - 0639FF = Collision array normal
  
• 063A00 - 0649FF = Collision array rotated (for 90 degree collision with loops and sharp curvers/walls)

Using the collision ID we collected, we can reference the correct angle the block is using (062900 + Collision ID = offset of the block's angle ID). We can also reference the collision array. To brief aside about the collision array, this is a series of values that represent a soldity shape that the block has, be it a curve of some kind, or just a flat solid surface. Each collision block is 10 bytes big, this means:

• Collision ID 00 = 062A00 - 062A0F (Collision block 00)
  
• Collision ID 01 = 062A10 - 062A1F (Collision block 01)
  
• Collision ID 02 = 062A20 - 062A2F (Collision block 02)
  
• Collision ID 03 = 062A20 - 062A2F (Collision block 03)
  
• etc, etc...

Each byte of the collision block is a solid height from left to right of the block, for example: 00 00 00 00 00 00 00 01 02 03 04 06 07 08 0A 0B will give you:


If the number is positive from 00 to 0F, the solid starts from the bottom and rises to the top (for floor pieces).
If the number is negative from FF to F1, the solid starts from the top and drops to the bottom (for ceiling pieces).

The exact same method is used for the rotated collision, except, the numbers would be from left to right, and right to left (depending on positive or negative): 00 00 00 00 00 01 02 02 03 04 05 05 06 07 08 09


It is extraordinarily complicated, and one thing to explain, yet another to understand. The design (in my opinion) is the work of pure genius, and when understood, you can begin to appreciate the efforts that went into constructing a format, that provides a nice balance between speed and memory usage. For large level construction it is the most ideal.

For more information about the format, see this page: http://info.sonicret...g/Level_Editing

So then the solidity is not what I need. Is there any easy way to check if there's a "ground" tile (a tile useful to the map) at a location vs. a "background" or "air" tile? Basically that's what I'm trying to accomplish in the long run.

[flamewing]

I think your best bet is to pass the word you get from the chunk table (solidity bits + flip bits + block ID) to the AI and let it learn what the each combination means on its own. The block IDs are used in indices to the collision arrays, which depend on the zone; and the solidity + flip bits will affect how the collision arrays are applied (if at all). But each block ID + solidity + flip bits will always act the same way in the same zone, meaning it can be thought of as a denser way to feed data to the AI than breaking everything up all the way down to the collision arrays. The drawback is that you will have to evolve the AI for a specific zone, and probably for a longer period of time until it learns how all relevant blocks work.

If you do it another way, you will run the risk of the AI not being able to pass the simplest of levels because it gets stuck holding right on sloped ground where you need speed.

Oh, and a pitfall: some chunks in the level layout in S1 have bit 7 set (that is, ID >= 128). This is a bit flag; it is used by loops to mark that the chunk with ID+1 holds the collision data when you are going through the loop. You may want to feed that bit to the AI too, if it is to have a hope of getting through GHZ1.

[MarkeyJester]

er1c1996, on 08 July 2015 - 06:58 PM, said:

So then the solidity is not what I need. Is there any easy way to check if there's a "ground" tile (a tile useful to the map) at a location vs. a "background" or "air" tile? Basically that's what I'm trying to accomplish in the long run.

Your only 100% way of detecting if a block is a floor, wall or ceiling of some kind, is by checking a combination of things:

• Collect the chunk ID. If it is 00, then all blocks will automatically be 0000 (therefore it is safe to assume it is nothing but an air block). If not, then...
  
• Collect the block from the chunk. If it's SS bits are both 00, then there is no collision (it's either an air block, or a "background" (foreground design) block). If not, then...
  
• Using the block ID, collect the collision ID from the collision table, and use that collision ID to reference the correct collision array block (10 bytes), if all of those 10 bytes are 00, then the block won't have any effect (treat it as air/background). If not, then it is a solid floor/wall/ceiling block of some kind.

Unfortunately, comparing it to Mario, you're looking at a difficulty step like no other. Certain slopes will cause Sonic to slow down at a gradual pace, so you'd need to take the angle into consideration, and decide if Sonic should continue running up the slope, or go back and take a run up. It'll be the case of Speed vs Angle. However, judging by the Mario one, it seems the I/O was able to keep up a good pace, if it can do the same for Sonic, then it is possible that checking for slopes can be avoided entirely. I was also going to point out the whole "top solid"/"left, right, bottom solid"/"all solid" issue, but Mario also has top solid situations, so I assume that one's covered.

[KingofHarts]

I fail to see why it couldn't work on Marble or Labyrinth in future iterations. Just needs work done in order to teach the ai to know when to go left.