News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: Landstalker  (Read 4347 times)

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Landstalker
« on: June 04, 2020, 03:21:57 am »
I've been working for a few years now on a disassembly of the classic Sega Genesis action RPG Landstalker. Thanks to the lockdown, I have been able to make a lot more progress.

I have a working disassembly on GitHub as a work-in-progress (https://github.com/lordmir/landstalker_disasm). Currently, the "disassembly" folder contains the full disassembly of the ROM, including the assembler source. Some functions have been documented, but there is a lot left that has not been.

Data sections and assets have been identified and extracted, including level maps and various graphics. Most of the game data has been compressed using various algorithms. I have worked out most of the algorithms but haven't yet developed effective re-compression routines yet. Most of the tile data has been compressed using a variation of the LZ77 algorithm - I have also included a tool that allows graphics to be extracted and recompressed.

I also maintain another two Landstalker repos, https://github.com/lordmir/landstalker_tools and https://github.com/lordmir/landstalker_gfx. Landstalker tools is a package of standalone executables that are designed to work from the command line. Currently, there are only two tools - one for compressing/decompressing the LZ77 graphics mentioned earlier, and another for converting palettes between the native binary Genesis format and the Tile Layer Pro format.

The Landstalker_Gfx repo is very much a work-in-progress. It is intended to be a full level editor for the game, but currently it can only display images of the various rooms and sprites. It has been developed in C++ using the multi-platform wxWidgets library, so it should be buildable and work on any platform. The aim is to turn it into a full level editor. The following screenshot is of the graphics viewer/editor.


Thirteen 1355

  • Hero Member
  • *****
  • Posts: 568
    • View Profile
Re: Landstalker
« Reply #1 on: June 04, 2020, 02:28:38 pm »
Wow, Landstalker! Now that's a game I didn't expect to show up here. This seems like a real interesting endeavor. I haven't played the game yet, the controls take some getting used to. Still, this is something worth following.
Helicoptering about till I find some ROM hacking treasure.

GhaleonUnlimited

  • Jr. Member
  • **
  • Posts: 37
    • View Profile
Re: Landstalker
« Reply #2 on: June 04, 2020, 03:08:38 pm »
That's amazing! I'm a really big Climax fan (but still haven't delved into Landstalker), and I'll look forward to seeing what comes out of this.  I'll def have a look when it's done, too. Thanks for working on this!

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Re: Landstalker
« Reply #3 on: June 04, 2020, 03:25:27 pm »
Thanks!

Talking of controls, in theory it wouldn't be too difficult to change the controls. Nigel will still be locked to the diagonal axis, but the controls could be changed to respond to UP,DOWN,LEFT,RIGHT instead of diagonals if that is something that would make it easier.

The file code\gamelogic\gamelogic1.asm in the disassembly contains a jump table on line 268 for handling the different controller direction combinations. These jumps could be changed so that the traditional U/D/L/R buttons respond to movement rather than diagonals (UL/UR/DL/DR).

One of the other ideas I was thinking of would be to add a shadow to assist with jumps. That would be a lot more complicated to add, however.

I have to admit, it took me quite a while to get used to the controls. Once you got used to them, it does become second nature.

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Re: Landstalker
« Reply #4 on: June 04, 2020, 03:39:30 pm »
Just for fun, I wanted to see how easy it would be to "fix" the controls. It so happens that it was quite straightforward - I've uploaded an IPS patch for the US ROM. Note that character movements on screen are still locked to diagonals, it is just that the traditional U/D/L/R can be used to control Nigel rather than having to use diagonals - Nigel will move NW when UP is pressed, SE when DOWN is pressed, NE when RIGHT is pressed and SW when LEFT is pressed.
https://filebin.net/6b24f8mbmnz7t8nc

Morinis

  • Sr. Member
  • ****
  • Posts: 465
    • View Profile
Re: Landstalker
« Reply #5 on: June 04, 2020, 05:01:46 pm »
I literally had to take a second look.  Landstalker of all things.  Definitely will be trying this one out  :beer:
YouTube: https://www.youtube.com/channel/UCK5S3RZCjv0O6FmXlSgmHXg


"If you get offended by my honesty then re-evaluate your hobbies on here."

Mindflower

  • Full Member
  • ***
  • Posts: 107
    • View Profile
Re: Landstalker
« Reply #6 on: June 04, 2020, 06:23:46 pm »
Yeah! =)


Looking forward to this!


Remember good times trying to jump on the fast chicken in one of the first villages and having an extraordinarily good laugh with friends. aaaahh good times.
« Last Edit: June 05, 2020, 10:26:50 am by Mindflower »

the_E_y_Es

  • Jr. Member
  • **
  • Posts: 49
    • View Profile
Re: Landstalker
« Reply #7 on: June 05, 2020, 12:14:31 pm »
My prayers have been answered. I love Landstalker. Once in a while I check youtube or even google for anything related to it, especially hacking projects.

A level editor would be amazing. Just imagine, I could make Mercator twice is size, maybe even add some extra quests. Something I always wanted is to have Friday use antidotes on Nigel when he's poisoned. She already resurrects him with Eke-eke's, so I wanted to grab that routine/animation and make it work with it other items as well. Kind of amplify her role in the gameplay. I think it would be really cool.

I'm ecstatic to see your project. I'll be following your progress with great interest.

G061

  • Jr. Member
  • **
  • Posts: 24
    • View Profile
Re: Landstalker
« Reply #8 on: June 06, 2020, 01:46:10 am »
I'm much the same as the person above. This game to me was my Zelda growing up, along with Crusader of Centy, but it was mostly Landstalker.
I'm a huge layman when it comes to this stuff though but I assume the point of this is to someday have something like Sonic 3 AIR/Mario 64 PC Port? Like a game-specific emulator or native pc port that runs the game outside of megadrive/genesis restrictions? Or is it just to document the game phsyics/assets?

Super interesting either way. I think too often about that cancelled Landstalker PSP remake, anything to give this game more exposure, it's very special to me so thank you for your work.

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Re: Landstalker
« Reply #9 on: June 06, 2020, 07:40:06 am »
Thanks all for the comments.

The main intention at the moment is to reverse engineer the various data structures used in the game (e.g. graphics, tile maps, strings, script actions, sprites, etc.) and to provide utilities to change these to make a new ROM. Ultimately, what I would like to create is a full game editor that will let you modify as much of the game as possible via a convenient UI. However, at the moment, things are in more of a proof-of-concept stage - many of the assets that I mentioned previously are compressed with custom routines, so new tools need to be developed in order to extract and re-compress these assets. Speaking of which, I have now added a new tool to extract/compress the tilemaps used to display 2D images (e.g. the Island Map or the game's title sequence). So we should be able to insert fully custom images in place of the originals now (the tile graphics and palette data formats have already been reverse engineered).

One of the nice things about having a disassembly is that this process is made a lot easier. One of the big challenges that can be faced when working with ROMs is how to re-insert new data into an existing ROM. This is very true with Landstalker, where there isn't a lot of free space on the 2MByte ROM - and what free space there is, is usually found in inconvenient locations. "Re-arranging" the ROM can be tricky - moving sections about can break pointers in existing code, and may not yield that much free space. The nice thing about having the disassembled code is that it gives you a lot more flexibility about how the ROM should be structured, thereby overcoming these issues. For instance, it should be possible to make a 4MByte+ ROM that still works without too much difficulty, which would allow users to create a lot more levels, etc. than existed in the original game.

A bonus of having the disassembly is that the game's code can also be expanded without having to worry about finding free space to insert opcodes in the ROM. It will require a certain amount of knowledge of 68k assembler, but, once relevant code sections have been identified, it shouldn't be too difficult to add new behaviour/functionality into the game. An example of this is the game's script. A big chunk of it is written in assembler - see file disassembly\code\script\characters\script_charactertable.asm - this is the code that is responsible for determining what lines each character says, or if any custom actions need to occur (such as the player receiving an item). It also handles the Yes/No prompts you sometimes get as well as setting of certain progress flags in order to move the game on. Having this data as an assembly file (with some custom macros to handle converting script indexes into the weird PC-relative offset format the ROM expects) makes modification a lot easier than just dealing with a block of data.

Of course, the game code could be used for more than this - e.g. as G061 suggested, knowledge of the game's code could be used to make a PC port. I believe a similar approach was taken with Sonic Mania - the code that handles the game physics was adapted from a disassembly of one of the original Sonic games IIRC. That is why the game physics in Mania is so similar to the originals.

June 07, 2020, 06:32:19 pm - (Auto Merged - Double Posts are not allowed before 7 days.)
So, an update.

I've now fully reverse engineered the map compression algorithm. It is a bit of a nasty beast, using a combination of LZ77 using a fixed offset dictionary, RLE of LZ77 commands in the vertical and diagonal directions, and finally more RLE to encode the remaining tiles based off of a tile dictionary. Unfortunately, my version of the compression algorithm isn't as good as the original game's, with my compressed maps being about 6% larger than the originals. This discrepancy adds up to around 30kbytes once all the maps have been decompressed and recompressed (all 642 of them!).

This difference is too large to allow the maps to be nicely inserted back into the ROM without overwriting other data, so I have instead decided to expand the original ROM to 4 megabytes, which leaves a little more than 2MBytes of free space to use.

The nice thing is now it is possible to make your own maps for Landstalker:



This is a screenshot of my first attempt at making a map - I added the new house and changed the bear statue into a tree. So far, I have tested it in the emulator and on the real console without issue. Hopefully, this will lead on to being able to develop more complex maps once proper tools are available. 

Making the maps is a bit tricky, as there are a few concepts you need to be aware of. Firstly, the viewable area is divided up into 16x16 "blocks" containing 4 tiles. These blocks are arranged in a staggered format: e.g. for a 3x2 map:
Code: [Select]
          ____
     ____| #0 |____
    | #3 |____| #1 |____
    |____| #4 |____| #2 |
         |____| #5 |____|
              |____|

This staggered arrangement is how the game handles the isometric effect. Blocks are defined in a separate data structure, based off of a combination of four tiles plus their attributes (priority, vertical-flip, horizontal-flip).

Secondly, there are in effect three tile layers. The first tile layer is the background - as the name suggests, the background is the layer behind all others. The foreground layer can be effectively split into two parts - background decoration and foreground.

Background decoration includes things like stones, signs, etc. They form an additional part of the background layer. Foreground includes all tiles that can appear in front of the player and other sprites - this is the layer that adds depth perception - i.e. you can be behind or in front of certain parts of the room.

The difference between decoration and foreground is whether the priority bit is set. This bit allows certain tiles to be drawn over sprites that do not have the priority bit set. Again, this is how it is possible for objects to appear in front of or behind objects.

Just to make things more confusing, the foreground layer is not directly on top of the background layer - it is actually shifted 16 pixels to the left. This means that blocks drawn in the foreground layer do not fully cover blocks drawn in the background layer - they will be either be 8 pixels above or 8 pixels below.

Finally, there is the heightmap. This is the data structure that determines what blocks are solid or not and at what height, and whether blocks have any special effects (spikes, etc). This layer is also used by the game to calculate whether a sprite should be behind or in front of the foreground.

At the moment, these three layers exist in their decompressed forms as csv files. Now that the hard work has been done in reverse engineering the decompression routines and coming up with suitable compression routines that work, we won't be too far away from having a full level editor available for Landstalker.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
« Last Edit: June 07, 2020, 06:35:53 pm by lordmir »

Gufino2

  • Newbie
  • *
  • Posts: 2
    • View Profile
Re: Landstalker
« Reply #10 on: June 08, 2020, 05:55:46 am »
Great Job, lordmir!  :thumbsup: :thumbsup:
I'll be glad to help you.
I'm working on the EU version of the rom (using Ghidra), and basically I'm in a situation similar to yours: I can extract all the sprites, tile maps and room data. Years ago I also reversed the Z80 audio driver and wrote a tool to extract the game BGMs in MIDI format, I hope the source code is not lost.

the_E_y_Es

  • Jr. Member
  • **
  • Posts: 49
    • View Profile
Re: Landstalker
« Reply #11 on: June 08, 2020, 05:41:24 pm »
Looks like the door to map editing has been pried open. Fantastic.

In the screenshot you provided there is a tree on the upper-left corner that appears over the house roof, instead of behind it. Is that because the priority bit for the tree is set? Thus making it foreground instead of decoration? Or is that caused by the heightmap setting for the tree?

If you don't mind my asking, will the disassembly be commented? Even small nuggets of information would be really interesting to read.

I might be a purist but I'd rather have a Landstalker romhack than a PC port.

In any case, this is very exciting.


cospefogo

  • Full Member
  • ***
  • Posts: 159
  • "Take this silver dagger to save your neck."
    • View Profile
    • Fliperamas
Re: Landstalker
« Reply #12 on: June 10, 2020, 09:02:49 am »
Talking of controls, in theory it wouldn't be too difficult to change the controls. Nigel will still be locked to the diagonal axis, but the controls could be changed to respond to UP,DOWN,LEFT,RIGHT instead of diagonals if that is something that would make it easier.

The file code\gamelogic\gamelogic1.asm in the disassembly contains a jump table on line 268 for handling the different controller direction combinations. These jumps could be changed so that the traditional U/D/L/R buttons respond to movement rather than diagonals (UL/UR/DL/DR).

One of the other ideas I was thinking of would be to add a shadow to assist with jumps. That would be a lot more complicated to add, however.

I have to admit, it took me quite a while to get used to the controls. Once you got used to them, it does become second nature.

Lordmir!

I was about to say — THERE IS ALREADY a patch on ROMHACKING that MODIFIES the CONTROLS — but it is nowhere to be found! At same time I can guarantee it is true because I still have the ROM patched down here. My Landstalker uses U/D/L/R for movement, instead of diagonals. I can share the patch privately if one wants for debugging purposes [PM me, please].

However I never had the courage to face Landstalker until today — and it is exactly NOT HAVING A SHADOW that really bugs me so much. It could be perfect to have such addition to better orientate the player.

I will follow closely this topic!
Cheers!
"Replicants are like any other machine - they're either a benefit or a hazard.
If they're a benefit, it's not my problem."

mziab

  • Sr. Member
  • ****
  • Posts: 313
    • View Profile
    • mteam
Re: Landstalker
« Reply #13 on: June 10, 2020, 11:37:51 am »
Lordmir!

I was about to say — THERE IS ALREADY a patch on ROMHACKING that MODIFIES the CONTROLS — but it is nowhere to be found! At same time I can guarantee it is true because I still have the ROM patched down here. My Landstalker uses U/D/L/R for movement, instead of diagonals. I can share the patch privately if one wants for debugging purposes [PM me, please].

However I never had the courage to face Landstalker until today — and it is exactly NOT HAVING A SHADOW that really bugs me so much. It could be perfect to have such addition to better orientate the player.

I will follow closely this topic!
Cheers!

Hiei-'s mirror of the patch seems to still be up, actually.

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Re: Landstalker
« Reply #14 on: June 11, 2020, 11:31:04 am »
Hi Gufino2! Massive thanks for your Landstalker Translation Tool - it has been really useful in finding and decoding compressed images and text, and really helped me get started in decoding the original ROM. Feel free to use any parts of my disassembly for your project. Your original notes that came with the tool are what got me involved in researching Huffman, etc., when I started decoding the ROM.

That would be really good if you did have any info on the music formats - I have made a start on disassembling the Z80 sound driver, but haven't got very far with it yet.

In answers to the_E_y_Es' questions:

Quote
In the screenshot you provided there is a tree on the upper-left corner that appears over the house roof, instead of behind it. Is that because the priority bit for the tree is set? Thus making it foreground instead of decoration?

Correct. If you look at the original map for Massan, you will notice that you cannot travel behind the right wall of any of the buildings. This is deliberate, as the blockset for that map does not have the priority bit set for that wall. This could be fixed by updating the blockset to set the priority bits for those tiles.

A lot of the maps in Landstalker have this limitation - the game developers would put flowerbeds, trees and other untraversable tiles between houses to prevent the player from walking between them, except for instances where this is allowed.

It should be noted as well that the tree in the background is not part of the map, instead it is a sprite. These trees can be removed later on in the game in order to access other areas.

Quote
If you don't mind my asking, will the disassembly be commented?
I have been commenting / naming as I go - however, as you can imagine, documenting the entire codebase is going to be a very large task - there are 90,000+ lines in total! I'll generally be adding comments to functions that have been reverse engineered, but for now the priority is in reverse-engineering the data structures to allow new content to be added.

Quote
I might be a purist but I'd rather have a Landstalker romhack than a PC port.

So far, the re-assembly works on modern emulators as well as official hardware. The expanded ROM has around 2 Megabytes of free contiguous space - more, once code sections have been 'reorganised' into one place. This should give us a lot of flexibility in terms of future rom-hacks.
« Last Edit: June 11, 2020, 11:40:46 am by lordmir »

the_E_y_Es

  • Jr. Member
  • **
  • Posts: 49
    • View Profile
Re: Landstalker
« Reply #15 on: June 17, 2020, 02:33:16 pm »
Cool. I'd love to examine the maps in the game, to better understand their design, geography and especially the tiling. So when it's time to create or expand an existing map, I can make it look consistent with the original style and not something that's obviously tacked-on.

Been kind of daydreaming about the possibilities.

Do you mind if I link this thread on other sites, like youtube? I know some people might be interested in this.

lordmir

  • Jr. Member
  • **
  • Posts: 6
    • View Profile
Re: Landstalker
« Reply #16 on: June 24, 2020, 01:34:12 am »
Hi,

No problem at all with linking to other sites, it would be good to see people interested in modding the game :)


I've made a release for the map viewer/editor so far - see https://github.com/lordmir/landstalker_gfx/releases/tag/0.1beta for Windows. That way, you can see how the maps have been constructed.

The disassembly contains an 'unpacked' folder that contains the decompressed map files in CSV format if you want to have a go yourself at editing them. The map compression tool I released will let you convert to/from compressed map formats that you can then re-assemble into the game. Let me know if you want some help doing this.

Ultimately, I would also want the LS Graphics Viewer to operate on the disassembly rather than the raw ROM - it makes life a lot easier, especially when re-inserting maps that may be of a different size to the original. It would also make working on the different ROMS (BETA, US, JP, UK, FR, DE) easier as well, as important data is kept at different offsets for each release.

Another small update - I've also reverse-engineered the string formats in this game as well. The strings tool will let you convert the uncompressed and compressed game text to/from ASCII.

I've added in a heightmap display overlay as well, if you enable the 'heightmap' checkbox you should see a 3-D overlay showing the heightmap. You can also expand the map entry and select heightmap from there - that will show the heightmap data in a 2D table format, useful for seeing data that would not normally be visible.

The colour of the heightmap indicates the tile restrictions: green: none, blue: no NPC allowed, red: no player or NPC allowed, purple: locked door, yellow: raft track. The number printed in the grid is also used to indicate the tile properties:
DOOR NORTH-EAST:   01
DOOR SOUTH-EAST:   02
DOOR SOUTH-WEST:   03
DOOR NORTH-WEST:   04
STAIRS:            05
DOOR WARP:         06
PIT:               07
WARP PAD:          08
LADDER NORTH-WEST: 0B
LADDER NORTH-EAST: 0C
COUNTER:           0E
ELEVATOR:          0F
SPIKES:            10
SIGN_NW1:          11
SIGN_NW2:          12
SIGN_NW3:          13
SIGN_NW4:          14
SIGN_NE1:          15
SIGN_NE2:          16
SIGN_NE3:          17
SIGN_NE4:          18
SWAMP:             19
LOCKED_DOOR:       1A
SIGN_NW5:          1E
SIGN_NW6:          1F
SIGN_NW7:          20
SIGN_NW8:          21
SIGN_NE5:          22
SIGN_NE6:          23
SIGN_NE7:          24
SIGN_NE8:          25
LOCKED_DOOR_SE:    26
LOCKED_DOOR_SW:    27
NOLE_STAIRCASE:    28
LAVA:              29
ICE_NE:            2A
ICE_SE:            2B
ICE_SW:            2C
ICE_NW:            2D
GODDESS_STATUE:    2E

The actual tile data isn't shown yet, however you can change the visibility and opacity of the different layers, which should give some indication into how the maps are made up.

Future updates aim to add in sprites, as well as more map properties (warps, flags, etc). An actual map editor shouldn't be too far away as well.

Have fun!