Gateway to Apshai Map Generator

[Kroah]

Hi all,

 

I've just finished to reverse engineer the map generation part of the game 'Gateway to Apshai'.

 

I've done an utility you can download in attachment to show the process of the generation and the resulting map with all the items, monsters, traps and chests. For now, the seeds are the ones from the original game, but maybe i'll add the possibility to choose any seed you want.

 

I've copy/pasted the readme file here.

 

Gateway to Apshai Utility - v1.00 by Kroah

==========================================

 

This utility allows you to generate the dungeon maps of the game 'Gateway to

Apshai'. It's based on a disassembled dump of the Atari PAL version (50Hz).

The ATR file used is included in the archive (CRC32 0xD60949B2).

 

The generation can be done step-by-step by clicking on the corresponding

checkbox 'Step by Step' and iterating with the button 'Iterate' (Easy ?

You can uncheck the checkbox to stop the step-by-step mode.

 

The map can be saved at any moment to a PNG picture.

 

Items, monsters, traps and chests can be clicked on the map (or on the list at

the right) and some informations will appear in the bottom right panel.

 

The game is split in 8 levels (beginning at level 1) and at each level, the

player is asked to choose among 16 dungeons.

 

 

Known bug in the game

---------------------

The Dungeon 8 from Level 7 seems bugged, the generation never end. Both

this utility and the game can't produce this map (never tested on a true

Atari or with the cartridge version). Someone confirms ?

 

 

Prerequisite

------------

This utility is written in C# and needs the Microsoft Framework .NET 2.0.

It won't run without it and will crash as soon as you'll launch it. You only

need the the 'Redistributable Package' not the SDK (Software Development Kit).

 

You can download the '.NET Framework Version 2.0 Redistributable Package' at:

 

http://msdn.microsoft.com/netframework/dow...es/default.aspx

 

 

Contact

-------

If you have some questions, want to leave me a word or simply discuss, you

can contact me by email or through my forum at my decompilation website:

 

http://bringerp.free.fr/RE/

 

 

Releases

--------

 

v1.00 Initial release.

 

Have Fun !

Kroah

(Pascal BRINGER)

GatewayToApshaiUtility___v1.00.zip

Edited September 18, 2006 by Kroah

[Rybags]

Being able to change the seed would be good.

 

You could incorporate a feature that automatically generates the right patched .ROM image in that case.

[Heaven/TQA]

could be usefull for me...

[Heaven/TQA]

and good to see your return of heracles stuff...

[Kroah]

Thank you for your kind words.

 

Like i've said in the ReadMe, the Dungeon 8 from Level 7 loops endlessly.

 

Could someone tests the cartridge version on a real Atari ? It's easy to do (Supposing you have the hardware) because you can skip each level until the level 7 and choose the dungeon 8.

 

I've tried 3 different disk version of the game, but i had the same result. Never tested the cartridge version, nor the apple II version (dunno if they have the same dungeon generator algorithm though...).

 

Being able to change the seed would be good.

 

You could incorporate a feature that automatically generates the right patched .ROM image in that case.

 

Huhu, i like this feature !

[Kroah]

I've added the feature suggested by Rybags. You can now play the game with the seeds you have carefully chosen. Some maps are really interesting, some are... really ugly

 

But i still think this map generator is surprising for its time Another game having a good random map generator (some years later) is 'Captive'. I have the original generator for PC created by mindscape in 1992 and it's... surprising for its time too.

 

Have fun !

 

v1.01

Added: The seed of each dungeon can be modified.

Added: Load feature which can get the seeds from an existing ATR image of the game.

Added: Save feature which can put the seeds to a new working ATR image of the game.

GatewayToApshaiUtility___v1.01.zip

Edited September 18, 2006 by Kroah

[DanBoris]

Do you plan to release the source code for this? I would be really interested to see the algorithm.

 

I have been studying the game Telengard recently and it has a really interesting way of generating it's map. The map in Telengard is huge, 50 levels with 2,000,000 rooms, but it doesn't generate if randomly. It has a clever little algorithm that generates the map mathematically so that it's the same every time you play the game.

 

Dan

[Kroah]

Do you plan to release the source code for this? I would be really interested to see the algorithm.

 

Yes, i'll release the source code with the binary soon. I clean a little the code of the algorithm because it's full of wonderfull gotos (thanks the old coding style in assembler ).

 

I have been studying the game Telengard recently and it has a really interesting way of generating it's map. The map in Telengard is huge, 50 levels with 2,000,000 rooms, but it doesn't generate if randomly. It has a clever little algorithm that generates the map mathematically so that it's the same every time you play the game.

 

In this game, the maps are randomly generated but are the same each game. The game uses an (ugly) random number generator to compute the sequence of random numbers. If the seed is the same, the sequence will be the same. That's why the maps are the same each game, but are programmatically generated 'randomly'. That's why the first step of this reverse engineering was to write the same random number generator the game uses. A good way to have a different sequence every game, is (generally) to use the clock as seed. But the developpers wanted fixed seeds to let the player learn the dungeons and choose the good and bad ones. The lack of memory prevented to store all the dungeons (9k per dungeon). So they've done a random map generator using fixed seed.

 

Does your word 'mathematically' mean the same thing ?

 

edit: spelling

Edited September 18, 2006 by Kroah

[Kroah]

By the way, has someone already seen a Staff or a Key in this game ?

Edited September 18, 2006 by Kroah

[iratanam]

Excellent Utility!! The Apshai series is one of my all time 8-bit Favorites!!

Edited September 18, 2006 by iratanam

[DanBoris]

Yes, this sounds very similar to how Telengard does it.

 

In this game, the maps are randomly generated but are the same each game. The game uses an (ugly) random number generator to compute the sequence of random numbers. If the seed is the same, the sequence will be the same. That's why the maps are the same each game, but are programmatically generated 'randomly'. That's why the first step of this reverse engineering was to write the same random number generator the game uses. A good way to have a different sequence every game, is (generally) to use the clock as seed. But the developpers wanted fixed seeds to let the player learn the dungeons and choose the good and bad ones. The lack of memory prevented to store all the dungeons (9k per dungeon). So they've done a random map generator using fixed seed.

 

Does your word 'mathematically' mean the same thing ?

 

edit: spelling

[Heaven/TQA]

dan, we call this "random map generator" as it is based on random algorithm which is fed by seeds so you can recreate the levels each time again... --> diablo 1+2... or nethack...or rogue...

[Heaven/TQA]

and if you are really interested why not read through our diablo topic?

[Kroah]

Hi BLarry71,

 

You have sent me a PM. Your question is interesting, and i think it's not really off topic. That's why i'll answer it in this forum, some people could found it useful

 

hello,

I have never seen the key or staff appear in the game! I see them in the code but how did you get pictures of them?

When you play a dungeon, the level is stored from $1000 to $2FFF. The player start at X cell 32, Y cell 5 (for dungeon 1 level 1). The width of a map is 128 cells, so a cell in front of the player is at adress $1000+32*128+5+(2 or 3 cells) = $2007. You can pock this cell with a number and you'll see the objects of the game, but you can't pick it up because the item is not added to the list in the dungeon (Most objects are split in 2 cells, $24 and $25 for the staff for example). Only 6 bits ($00-$3F) are used (bit 7 holds the information 'discovered (0) or not (1)' and bit 8 holds 'if the cell is passable (0) or not (1)').

 

1 byte:

$00 Wall

$01 Door

$02 Secret Door

$03 Floor

$04 Floor border

 

2 bytes:

$08 Key

$0A Armor

$0C Weapon

$0E Spell

$12 Bow

$14 Arrows

$16 Potion

$18 Shield

$1A Gauntlet

$1C Amulet

$1E Helm

$20 Wand

$22 Cross

$24 Staff

$26 Trap

$2E Chest

$3F Extern

 

Calls the debugger (F8) when you just start level 1 dungeon 1 and types:

c 2007 24

c 2008 25

 

Also do you know what these letters are for? They look like upside-down "FC"

 

0fc1 |  X   X |
0fc2 |  X  X X|
0fc3 |  XX X  |
0fc4 |  XX X  |
0fc5 |  X  X X|
0fc6 |  XX  X |

 

It's a coincidence, the adress $0fc0 and following are part of the end level bonus code (by the way it looks like the death of jumpman too ):

 

[...]
0FB6	 INC strengthMax
0FB9	 INC strengthRealTime
0FBA
0FBC loc_0FBC:
0FBC	 LDA console; 001: luck
				; 010: strength
				; 100: agility

0FBE	 AND #4
0FC0	 BEQ $0FD3
0FC2	 LDX #19
0FC4 loc_0FC4:
0FC4	 LDA string6,X	   ; __HIGHER_AGILITY!__
[...]

 

I'm doing the Gateway to Apshai part of my website, you'll be able to see the effect of the Wand (as if it was generated in the dungeon... Suspense !)

 

Regards,

Kroah

[Tempest]

There are a few items in GtA that I never could figure out what they do, the Wand and Cross being two of them (I assume the Cross did something to Vampires but it never worked for me). I wasn't aware there was a key or staff in the game at all, interesting...

 

Tempest

[DanBoris]

dan, we call this "random map generator" as it is based on random algorithm which is fed by seeds so you can recreate the levels each time again... --> diablo 1+2... or nethack...or rogue...

 

I just took a closer look at Telengard and it doesn't use a random number generator. Here is the pseudo code for it's map generator:

 

Q=X*1.6915+Y*1.4278+Z*1.2462+X*1.4278+Y*1.2462+Z*1.6915:
HI = Q AND 255
Q=X*Y*1.2462+Y*Z*1.6915+Z*X*1.4278
IF Q & 0x03 != 0 THEN
Q = (Q >> 2) AND 0x0F
If Q  > 9 then Q = Q - 9
HI = HI + (Q << 8)
HI=HI+Q*256
END IF
HI = INT(HI)

 

X, Y, and Z are the room coordinates in the maze. Each level is 200x200 and there are 50 levels. The value of HI defines each room as follow:

 

bits 0-1: Top wall, 0 = no wall, 2 = wall, 3 = door

bits 2-3: Left wall, 0 = no wall, 2 = wall, 3 = door

 

bits 8-15: Special items, Inn, Pit, Teleporter, Starway, etc.

 

Dan

[Cybergoth]

Do you plan to release the source code for this? I would be really interested to see the algorithm.

 

I've been working on reverse-engineering GtA for a few years on and off as well. (A lot more years off than on actually )

 

Instead of working with a complete 64K memory dump (You know you're nuts Kroah, don't you? ), I've been just workin with the 16K cartridge binary

 

I never made it past the dungeon creation code, but Kroahs ultimate work finally made me see the light

 

So, by replacing all my unknown memory locations with his variable names and some of his label names as well, I now managed to fully analyse and understand the dungeon creation code. I labeled and commented it some more than Kroah did, so maybe this is what you were looking for Dan

 

@Kroah If you like it, feel free to add it to your page. I'll probably add more to it some day, but next I'll port it to plain C, as a base for a tool to create 2600 suitable data

 

BTW: The source code compiles into a working bit-perfect 16K GtA cartridge image, if you ever wanted to mess with this

GTAREV.zip

[Heaven/TQA]

it seems i have to have a closer look into the map generator...

[Heaven/TQA]

dan, i am just trying to understand your pseudo code but when i enter it into turbo basic xl... is this correct?

 

5 X=RAND(200):Y=RAND(200):Z=RAND(50)
8 PRINT X,Y,Z
10 Q=X*1.6915+Y*1.4278+Z*1.2462+X*1.4278+Y*1.2462+Z*1.6915
20 HI=Q&255
30 Q=X*Y*1.2462+Y*Z*1.6915+Y*X*1.4278
40 IF INT(Q)&3<>0
50   Q=Q DIV 4
60   Q=Q&$0F
70   IF Q>9 THEN Q=Q-9
80   HI=HI+(Q*256)
90 ENDIF 
100 HI=INT(HI)

[Heaven/TQA]

btw. the guy who did the telengard remake on PC did later on the game Fate...

[Delmoko]

Late to the party here, but I've been playing Gateway since the 80s... this utility with the maps is unbelievable. Thank you SO much!!!!

Btw... the Colecovision version has 99 dungeon choices per level!

I wish the Commodore version changed the colors of the walls like the Atari version... how lazy is that!

 

Your reverse engineering on MULE is awesome too... another favorite we still play to this day!

Simply amazing work!

 

"Your Mule was judged best built"