Distraction time

I recently posted a project page for Retail Clerk '90. That means it's time for me to get sidetracked with a different idea for a few months. I can justify it by saying it's an opportunity to see if the build tools for Retail Clerk '90 can be used for a different game.

I've had two game ideas swirling around in my head for a while:

1) Developing a game specifically made for speedrunning. I'm 100% positive other people are already doing this today. I'm not claiming it's an original idea. Dragster on the Atari 2600 is well over 40. It's just something I've been thinking about trying. I'm not a speedrunner myself but I enjoy watching them. A Vice City 100% speedrun helped me through a long flight once. Really, really short ones are great too. I mean like crazy short ones that don't use any glitches. I want to write a game demo that someone can solve in a few seconds if they know what to do.

2) Developing a game set in a skyscraper with an unorthodox elevator system. I'm not going to describe this well even though I can picture it perfectly. In every building I'm aware of there are regular elevators that stop at each floor in the building. In many tall buildings there are express elevators that skip some set of floors. Like in a 100 story building there might be an express elevator that goes to the 80th floor then visits all the subsequent floors. There are also elevators that just go directly from the 1st floor to the touristy observation deck at the top. The building I'm picturing has none of these. It has elevators that connect two specific floors. Imagine there are two elevator shafts that service every floor but only connect two floors at a time.

For example the 1st floor has two elevators that connect to the 5th and 16th floors. The 5th and 16th floors would then have elevators that connect back to the 1st floor and one other. The player has to find a route from the first floor to the top floor because that's where they work. It's similar to "Maze" by Christopher Manson but with much worse storytelling and artwork. I can't tell you how many hours I spent on that book in the 1980s.

Look, I don't know why someone developed a skyscraper that works like this. They're a very sick person. Hold on, wait, I guess I'm the one designing it. So then I don't know who would actually pay for a building like this. It doesn't matter. This is how the building is designed, deal with it.

It's easy to see how these two ideas could be merged. If there are multiple paths through the skyscraper then one must be fastest. It's similar to the traveling salesperson problem except each connection has a fixed weight.

This is an interesting game idea because there are goals like:

• Visit every floor
• Visit every floor exactly once
• Find the shortest path to the top
• Talk to everyone in the building and/or examine some arbitrary things in the building

I'm tentatively calling this idea "Speedrun Tower".

This premise is kind of neat but it's missing something... randomness. Yes, the connections between floors need to be randomized each time. There are problems of course. It's possible (perhaps likely) to create connections that make the game unsolvable.

What we need here is:

• A randomly generated guaranteed path to the top floor that traverses all floors
• A set of random floor connections that might introduce shortcuts

This means most floors really have 3 elevators:

1. Elevator that connects to the previous floor in the "guaranteed path"
2. Elevator that connects to the next floor in the "guaranteed path"
3. Elevator that connects to a floor in the "random path"

The first and final floors would only have two elevators - one connected to the "guaranteed path" and ther other connected to the "random path".

I originally thought this tower should be at least 40 floors with 120 being the ideal number. All my ideas start off all grandiose like this. I settled on 16 total floors. The first floor is the entrance and the final floor is the destination. Here's a picture if that helps:

If I ever turn this into a real demo it will likely have even fewer floors.

Building a guaranteed path is simple. Start at floor 0 (the entrance) and pick the floor it connects to, then pick the floor that connects to and so on. The last floor in the list connects to the destination floor.

There are many ways to accomplish this but I'm trying to think of one that isn't a nightmare to code on the Genesis.

Let's start with a list of floors:
0123456789ABCDEF

The guaranteed order needs to start with 0 and end with F. So our starting lists are:
Unlinked floors = 123456789ABCDE
Guaranteed order = 0______________F

There are 14 floors remaining so doing a MOD 14 against a random number will produce a number between 0-13. For example:
666%14=8

So we remove the 8th element in the unlinked floor list. We now have:
Unlinked floors = 12345678ABCDE
Guaranteed order = 09_____________F

Now we'll move to a MOD 13 on the remaining list:
666%13=3

So we remove the 3rd element in the unlinked floor list. We now have:
Unlinked floors = 1235678ABCDE
Guaranteed order = 094____________F

And so on until we get to the order:
0948AB15327D6CEF

In visual form that looks like:

Now we need a 2nd set of connections between the floors. To do that we'll go through the list and pick a 2nd pair for each floor.

Our list of floors again begins with:
0123456789ABCDEF

First we'll take floor 0 out because we don't want it to pair with itself. We now have:
123456789ABCDEF

Let's use a new random number and MOD 15 it against this list:
8964%15=9

So our first pairing is [0,A]. We then remove item 9 from the list and have:
12345678ABCDEF
[0A]

Repeat and we're at:
2345678ABCDEF
[0A] [1,?]

Now it's MOD 13:
8964%13=7

So we get to:
2345678BCDEF
[0A] [19]

And so on until we end at:
[0A] [19] [2F] [34] [5C] [6E] [78] [BD]

Here's that is in visual form:

The shortest path then is.. hmm.. maybe
0->9->4->8->7->2->F

I'm going to test it out in Java first because I can write that in just under 5 minutes:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class FloorRandomizer{

	public static void main(String[] args){
		String[] guaranteedPathFloors={"1","2","3","4","5","6","7","8","9","A","B","C","D","E"};
		String[] allFloors={"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
		ArrayList<String> floorsA=new ArrayList<String>();
		Collections.addAll(floorsA,guaranteedPathFloors);
		StringBuilder guaranteedPath=new StringBuilder("0");
		Random r=new Random();
		//replace with hardcoded "int randA=666;" to test the example on the page
		int randA=Math.abs(r.nextInt());
		int startSize=guaranteedPathFloors.length;
		for(int i=startSize;i>0;i--){
			int mod=randA%i;
			guaranteedPath.append(floorsA.remove(mod));
		}
		guaranteedPath.append("F");
		ArrayList<String> floorsB=new ArrayList<String>();
		Collections.addAll(floorsB,allFloors);
		StringBuilder alternatePairs=new StringBuilder();
		//replace with hardcoded "int randB=8964;" to test the example on the page
		int randB=Math.abs(r.nextInt());
		startSize=allFloors.length;
		for(int i=startSize;i>0;i-=2){
			alternatePairs.append("[");
			alternatePairs.append(floorsB.remove(0));
			int mod=randB%(i-1);
			alternatePairs.append(floorsB.remove(mod));
			alternatePairs.append("] ");
		}
		System.out.println(guaranteedPath.toString());
		System.out.println(alternatePairs.toString());
	}
}

I tested with the previous hard-coded values to validate my thinking was correct.

Here are 10 other example sets it created using actual random numbers:

Guaranteed path: 0CAE27D58B19643F
The other connections: [01] [23] [4A] [5D] [6F] [78] [9B] [CE]
I like how this one has an elevator that looks normal at first.

Guaranteed path: 0C3928D6A41E7B5F
The other connections: [01] [23] [46] [57] [8D] [9A] [BC] [EF]
The random set looks very close to being normal and is just off enough to be confusing. It's great.

Guaranteed path: 02E563894B7D1CAF
The other connections: [04] [18] [23] [5A] [6C] [7E] [9B] [DF]
4 connects to 9 and B which also connect to each other, that will be confusing. This is also great.

Guaranteed path: 018D2C4B3A9765EF
The other connections: [08] [15] [2B] [3A] [46] [7D] [9E] [CF]
I thought this had a short solution at first but I was wrong. 0->5->6->4->C->F is the best I can find.

Guaranteed path: 0B9AE7D15432C68F
The other connections: [0F] [1C] [28] [36] [47] [5E] [9D] [AB]
This is the first example that can be completed in one step. It's totally fine with me that this will occur 1/15 times. I could prevent that but don't want to.

Guaranteed path: 087AC23E156D9B4F
The other connections: [0B] [18] [2F] [35] [47] [69] [AD] [CE]
0->B->4->F looks like the shortest path here.

Guaranteed path: 03C1658A72B49DEF
The other connections: [0A] [1B] [2E] [3C] [4F] [5D] [67] [89]
Sometimes the random set will have duplicates from the guaranteed set. Like 3<->C in this example. This is fine. Anything that makes the building seem more dysfunctional is a benefit.

Guaranteed path: 05E17A29B3648CDF
The other connections: [0A] [19] [24] [38] [5D] [6F] [7B] [CE]
0->5->D->F is likely the shortest path here.

Guaranteed path: 094B57E138D2C6AF
The other connections: [02] [1B] [34] [5A] [6F] [79] [8D] [CE] I don't see any way to get through this one quickly.

Guaranteed path: 0ACED2754B39861F
The other connections: [07] [15] [23] [46] [8B] [9C] [AD] [EF]
This looks like it could be difficult. 0->A->C->E->F is probably the shortest path. Veering off that path looks really confusing.

Doing this on the Sega Genesis is a little tougher because there is no random number generator. There are some things we can use that sort of roughly act like a random number though. Like:

1. Counting the number of vblanks that occur before the player presses a button - the Start button on a title screen being the most obvious one.
2. Counting how many vblanks occur while the user is pressing the Start button. These occur 60 times a second so even fast button pressers might have non-zero numbers here.
3. Sending the player to a second screen after the title screen where they have to make some other selection and counting how many vblanks occur on that page. Like, I dunno, picking which sprite they want to use for example.
4. Just plain asking the player to enter a number. I don't really like this idea though.
5. Instead of vblanks the number of times the main loop executes also might work. This allows for slight differences in results based on build version.
6. Hard coding a randomly generated number at compile time. I really don't like this idea.
7. Finding an undocumented register that returns garbage data on real hardware. This is unlikely to exist and almost certainly wouldn't work on emulators anyway.
8. Potentially adding some variables based on the detected controller type or other things plugged into the Genesis.
9. Crowdfund a Sega Genesis Model 4 that is identical to the original hardware except for including a random number generator. Convince naive technology sites to run headlines like "Sega is back in the hardware business!" about it. Hire a team with no experience implementing a project like this. Delay production for several years with increasingly flimsy excuses. Announce a wide range of retro titles that will be available for the system (all of which are widely available already) to create the illusion of third-party support. Finally, ship a system made from off-the-shelf hardware that runs emulators.

I think I'll start with the first, third, and fifth ideas together. This means a speedrunner could get the shortest possible path if they knew exactly which frames to hit buttons on. I don't think there's anything I can do to avoid this. I don't think there's anything I want to do to avoid this.

Oh great, I need to build a character select screen now too. Who are these characters anyway? Let's say they're Gen-Zers who just entered the workforce. I'm (hopefully obviously) a Gen-Xer and have two Gen-Z kids. I don't know if that name will stick or if they'll get something better. Gen-"Z" makes it sound like they're the last ever. That can't be completely ruled-out as unlikely as it is. Anyway, we collectively decided to make life really confusing for them. Especially the past few years. When they enter the workforce we'll find a way to make it complicated. Like making them navigate a series of nonsensical elevators.

Oh hey, so back to this demo idea. Here's the character select screen I'll use when it's real. These are all composite characters based on random friends of my kids whose names I will never remember.

While building this in 68000 assembly I will unintentionally implement arrays that shrink as elements are removed. That sounds fun.

This is all being built on top of the template project from the previous installment in this series. I don't plan to post this full code because this is more like a proof of concept. This has only been debugged to prove it works. It has not been optimized and I can see a few improvement opportunities while I'm reviewing it:

First we'll add some memory map constants:

MEM_RANDOM_1=$FFFF0000 ; first random number
MEM_RANDOM_2=$FFFF0002 ; second random number
MEM_FLOOR_QUEUE=$FFFF0004 ; queue of floors
MEM_GUARANTEED_ORDER=$FFFF0022 ; order of floors in the guaranteed path
MEM_RANDOM_ORDER=$FFFF0042 ; order of floors in the random paths

Then we'll build the guaranteed path:

	; hardcoded "random number" for demo purposes
	move.w	#$029A,(MEM_RANDOM_1)
	; hardcoded "random number" for demo purposes
	move.w	#$2304,(MEM_RANDOM_2)
	; build the floor queue
	lea	MEM_FLOOR_QUEUE,a0
	move.w	#$0001,(a0)+
	move.w	#$0002,(a0)+
	move.w	#$0003,(a0)+
	move.w	#$0004,(a0)+
	move.w	#$0005,(a0)+
	move.w	#$0006,(a0)+
	move.w	#$0007,(a0)+
	move.w	#$0008,(a0)+
	move.w	#$0009,(a0)+
	move.w	#$000A,(a0)+
	move.w	#$000B,(a0)+
	move.w	#$000C,(a0)+
	move.w	#$000D,(a0)+
	move.w	#$000E,(a0)+
	move.w	#$0000,(a0)+
	move.w	#$0000,(a0)+
	; use d7 to count the number of rooms that need to be sorted
	move.w	#$000E,d7 ; 14 rooms to sort since floors 0 and F are in fixed positions
	; build the guaranteed path
	lea MEM_GUARANTEED_ORDER,a1 ; point a1 to the guaranteed order
	move.w	#$0000,(a1)+ ; floor 0 is always first
BuildGuaranteedOrder:
	clr d0 ; clr done out of paranoia
	move.w	(MEM_RANDOM_1),d0
	clr	d1 ; clr done out of paranoia
	move.w	d7,d1 ; copy the value in d7 (floor counter) to d1
	divu	d1,d0 ; divu does divide + mod
	clr.w	d0 ; clear the quotient part
	swap	d0 ; move modulus to lower word
	move.w	d0,d1 ; need this value again later
	; move to the index in d0 on the floor queue
	mulu.w	#WORD_SIZE,d0 ; multiply by LWORD_SIZE to get offset
	lea MEM_FLOOR_QUEUE,a0 ; point a0 to the start of the floor queue	
	adda.l	d0,a0 ; move to offset
	move.w	(a0),(a1)+ ; copy the value from floor queue to guaranteed path
	; adjust the floor queue
	lea (2,a0),a2 ; point a2 to the word past the current entry in the floor queue
	move.w	d7,d6 ; move current size of list to d6
	sub.w	d1,d6 ; subtract the index of the item being removed
ReorderFloorQueue1:
	move.w (a2)+,(a0)+ ; shift values down
	dbra d6,ReorderFloorQueue1
	dbra d7,BuildGuaranteedOrder
	move.w	#$000F,(-2,a1) ; floor F is always last

Let's see if that worked:

Yup, we got 0948AB15327D6CEF as expected.

Next we'll build the random path:

	; re-build the floor queue
	lea	MEM_FLOOR_QUEUE,a0
	move.w	#$0001,(a0)+
	move.w	#$0002,(a0)+
	move.w	#$0003,(a0)+
	move.w	#$0004,(a0)+
	move.w	#$0005,(a0)+
	move.w	#$0006,(a0)+
	move.w	#$0007,(a0)+
	move.w	#$0008,(a0)+
	move.w	#$0009,(a0)+
	move.w	#$000A,(a0)+
	move.w	#$000B,(a0)+
	move.w	#$000C,(a0)+
	move.w	#$000D,(a0)+
	move.w	#$000E,(a0)+
	move.w	#$000F,(a0)+
	move.w	#$0000,(a0)+
	; use d7 to count the number of rooms that need to be sorted
	move.w	#$000F,d7 ; 15 rooms to sort since floors 0 and F are in fixed positions
	; build the guaranteed path
	lea MEM_RANDOM_ORDER,a1 ; point a1 to the guaranteed order
	move.w	#$0000,(a1)+ ; floor 0 is always first
BuildRandomOrder:
	clr d0 ; clr done out of paranoia
	move.w	(MEM_RANDOM_2),d0
	clr	d1 ; clr done out of paranoia
	move.w	d7,d1 ; copy the value in d7 (floor counter) to d1
	divu	d1,d0 ; divu does divide + mod
	clr.w	d0 ; clear the quotient part
	swap	d0 ; move modulus to lower word
	move.w	d0,d1 ; need this value again later
	; move to the index in d0 on the floor queue
	mulu.w	#WORD_SIZE,d0 ; multiply by LWORD_SIZE to get offset
	lea MEM_FLOOR_QUEUE,a0 ; point a0 to the start of the floor queue	
	adda.l	d0,a0 ; move to offset
	move.w	(a0),(a1)+ ; copy the value from floor queue to random path
	; adjust the floor queue
	lea (2,a0),a2 ; point a2 to the word past the current entry in the floor queue
	move.w	d7,d6 ; move current size of list to d6
	sub.w	d1,d6 ; subtract the index of the item being removed
ReorderFloorQueue2:
	move.w (a2)+,(a0)+ ; shift values down
	dbra d6,ReorderFloorQueue2
	; now move the first item in the floor queue to the random list
	lea MEM_FLOOR_QUEUE,a0 ; point a0 to the start of the floor queue		
	move.w	(a0),(a1)+ ; copy the value from floor queue to random path	
	lea (2,a0),a2 ; point a2 to the word past the current entry in the floor queue
	move.w	d7,d6 ; move current size of list to d6
ReorderFloorQueue3:
	move.w (a2)+,(a0)+ ; shift values down
	dbra d6,ReorderFloorQueue3
	sub.w	#$0002,d7
	bge.w	BuildRandomOrder

Let's see if that also worked:

This time we're expecting 0A192F345C6E78BD and it looks like that's what we got.

So I'm getting the expected values with static "random" numbers. Setting the random numbers based on when buttons are pressed means adding code like this in two places:

move.w	(MEM_MAINLOOP_COUNTER),(MEM_RANDOM_[1|2])

After that, we need to call the same code to build the paths. Here are two combinations produced from testing that:

Guaranteed path: 0D147AE5B639C28F
The other connections: [08] [17] [23] [4E] [5D] [6B] [9C] [AF]
So this one can be finished in two moves.

Guaranteed path: 03DA9C4167B2E58F
The other connections: [0C] [1D] [25] [37] [4A] [69] [8F] [BE]
With 8<->F appearing in both paths there aren't many great shortcuts.

So this was fun and worked better than I expected. Seriously. I dreamed up this idea a couple months ago and wrote the Java code. I was dreading trying to re-create it on the Genesis but it only took 2 hours. Now I'm all frustrated that I put it off so long.

Will this turn into an actual demo? It's tough to say right now. I like this idea a lot but designing 16 floors with scenery, people, and dialog isn't super appealing at the moment. If I do this idea there's a very good chance I will change the graphical style to use some (cheap) commercial tiles. I think that would cut the effort level down considerably.

I don't know what my next Genesis programming article will be. There's still a lot I want to learn so I doubt this will be the last.

Related