Trouble with object placement. Any suggestions?

[tokumaru]

Hey all. I was talking about the level format in my current project in another thread and Disch gave me a simple but great idea on how to improve it, so I felt I could try it again for object placement.

Without going into details about the level format, all that I need to say is that it's essentially a 2-dimensional array of indexes pointing to 256x256-pixel blocks that contain terrain information.

My initial idea to place objects in those "screens" was to point to a ROM location (16 bits, with the highest indicating the presence of objects) where the object definitions for each screen were, in addition to indicating what 256x256-pixel block to use. That'd work fine, but I'd need 3 bytes per "screen", and most of them don't have objects, so that sounds like a huge waste.

Now, I feel it's important that the objects placed in a screen are somehow tied to it, so that I can easily locate them when it's time to load them, and so that I can save a few bytes from not having to define the high bytes of their coordinates (because I already know the coordinates of the screen where they are), as opposed to many games that just hold a big list of objects/enemies sorted by X and Y coordinates (works great in games that do not scroll vertically, but not so much otherwise).

The first solution I could think of was to also index the object definitions of each screen, limiting them to 256 (only 256 screens from the level map would have objects - or they'd reuse each other's objects, but that doesn't work so well -, which seems kinda limited). Then, each screen in the level map would only use 2 bytes (instead of 3), one pointing to the screen map and the other pointing to the object definition block. But I'd have the overhead of creating a table to translate the object definition indexes into their locations.

Does anyone have any thoughts on this?

[Celius]

I'm not quite sure I understand what you're saying. Are you saying you're level is divided into "screens", and you have objects that you assign to those "screens", and you're wondering how to do it in a good way?

[tokumaru]

Basically, yes. The levels are composed by a 2-D arrangement of 256x256-pixel blocks ("screens"), and I'm looking for the best way to assign objects/enemies to them.

Today I though about having the following list to tie the object definitions to the screens where the objects are:

Code: Select all

	.db $01, $02	;screenX = $01, screenY = $02
	.dw Objects0102
	.db $01, $03	;screenX = $01, screenY = $03
	.dw Objects0103
	.db $01, $05	;screenX = $01, screenY = $05
	.dw Objects0105
	.db $02, $01	;screenX = $02, screenY = $01
	.dw Objects0201
	(...)

It's sorted first by X coordinate and then by Y coordinate. Then, when loading a screen, I'd look for it's coordinates in this list, in order to know where it's objects are defined. But I still can't think of an efficient way to locate a particular screen in this table.

The object definitions would follow the following format:

Code: Select all

Objects0102:
	;The following word contains the number
	;of objects in the screen, and the index
	;of one of 1024 state bits (to control the
	;alive/dead states of the objects)
	.dw $1421	;6 objects, index $021
	;Then follow the individual objects, the
	;next byte indicates the type, and the
	;rest varies according to the type
	.db $56	;Object type $56
	;Parameters for object type $56
	(...)
	.db $3A	;Object type $3A
	;Parameters for object type $3A
	(...)

Objects0103:
	.dw $0826	;3 objects, index $026
	.db $42	;Object type $42
	;Parameters for object type $42
	(...)

The state bits are needed so that enemies that have been killed are not loaded again. In fact they can even use more bits, to remember other things for the next time they are loaded. The state bit index defined in there is the one of the first object, and this number is incremented according to how many bits each object uses.

[Celius]

Well, maybe don't look it as a compilation of objects. Look at is a compilation of screens. So maybe do something like this:

Code: Select all

Screen1:
 .dw Object1, Object2 ...
Screen2:
 .dw SomeObject, AnotherObject, ...

That's what I'd do. You said you already knew the X, Y coords?

[tokumaru]

Code: Select all

Screen1:
 .dw Object1, Object2 ...
Screen2:
 .dw SomeObject, AnotherObject, ...

OK, but how do I easily find the location of "Screen1"? The only thing I have are the coordinates of it (X = 0, Y = 1). How does that help me find the objects defined under the label "Screen1", which should be the objects positioned in that screen?

This looks like what I was gonna do first, meaning I'd need 2 more bytes per screen (even the ones that do not have any objects) to point to the location where the objects are defined.

[Celius]

Today I though about having the following list to tie the object definitions to the screens where the objects are:

Code: Select all

	.db $01, $02	;screenX = $01, screenY = $02
	.dw Objects0102
	.db $01, $03	;screenX = $01, screenY = $03
	.dw Objects0103
	.db $01, $05	;screenX = $01, screenY = $05
	.dw Objects0105
	.db $02, $01	;screenX = $02, screenY = $01
	.dw Objects0201
	(...)

It's sorted first by X coordinate and then by Y coordinate. Then, when loading a screen, I'd look for it's coordinates in this list, in order to know where it's objects are defined. But I still can't think of an efficient way to locate a particular screen in this table.

I'm sorry, but I don't really understand what you mean by locating a particular screen. Could you clarify that for me?

And also, your level is a 2-dimensional grid of screens, correct? How many screens are there in a level? Do you start at a particular screen?

EDIT: What I meant in my post above was that instead of saying "Object 1 will go to Screen 1, Object 2 will go to Screen 2, Object 3 will go to screen 1, and Object 4 will go to screen 2", you should say something like "In screen 1, we'll have Objects 1 and 3, and in screen 2, we'll have objects 2 and 4." It's kind of like having them already come filed instead of having to file them, you know? Because it seems like in your code, you have a bunch of objects, and you have to file them to their specific screen. So instead of this:

Code: Select all

 .db $00, $01  ;ScreenX = 0, ScreenY = 1
 .dw Object1
 .db $00,$02
 .dw Object3
 .db $00, $01
 .dw Object2
 .db $00, $02
 .dw Object4

You should just have something like this:

Code: Select all

 .db $00, $01  ;ScreenX = 0, ScreenY = 1
 .dw Object1
 .dw Object2
 .db $00, $02 ;ScreenX = 0, ScreenY = 2
 .dw Object3
 .dw Object4

So you'll just have to lookup the screen one time, instead of once for each object. Am I making any sense? I don't know how you do with your X, Y positions of the objects in these screens, you'll have to clarify that more.

[tokumaru]

I'm sorry, but I don't really understand what you mean by locating a particular screen. Could you clarify that for me?

You are right, these things are really hard to explain. Let me try with an example. This is a very very simple level map:

Code: Select all

LevelMap1:
	.db $01, $01, $02, $06
	.db $00, $00, $09, $01

This is a really small level, just 4x2 "screens", or 1024x512 pixels. This just defines the map, not objects. Using the coordinates of the screens, I can find any of them easily with the following formula: LevelMap1 + (Y * 4) + X. For example, the screen at (2, 1):

LevelMap1 + (1 * 4) + 2 = LevelMap1 + 6

If you count 7 bytes (the first one is 0) starting from the label "LevelMap1", you'll find screen map number $09, which is indeed the one at location (2, 1). From that you can see that reading screens from the level map is very easy. Adding objects to that, however, is not. This is one way to do it:

Code: Select all

Level1Objects:
	.dw Scr0Obj, Scr1Obj, Scr2Obj, Scr3Obj
	.dw Scr4Obj, Scr5Obj, Scr6Obj, Scr7Obj

This other array holds the addresses of where the objects of each screen are defined. It is arranged just like the level map, so a simular formula can be used to easily locate the pointer, and use it to read the objects. This works great, but the problem is that many screens do not have any objects, and I'd be wasting an insane ammount of ROM bytes pointing to nothing.

And also, your level is a 2-dimensional grid of screens, correct? How many screens are there in a level? Do you start at a particular screen?

Width and height vary from 1 to 256, so any combination of the numbers in between that still fits in the ROM is valid (for example, the largest possible square level, without objects, would be 90x90 "screens", or 23040x23040 pixels). The size of the level, along with the starting location of the player are defined in the level header. Also, the player can die and start from the last checkpoint.

What I meant in my post above was that instead of saying "Object 1 will go to Screen 1, Object 2 will go to Screen 2, Object 3 will go to screen 1, and Object 4 will go to screen 2", you should say something like "In screen 1, we'll have Objects 1 and 3, and in screen 2, we'll have objects 2 and 4." It's kind of like having them already come filed instead of having to file them, you know?

If I understand you, the code I presented above is exactly that. It's just terribly inneficient space-wise.

Because it seems like in your code, you have a bunch of objects, and you have to file them to their specific screen.

Having to find the objects was just part of a solution that would require less ROM space. What I'm trying to find here is a compromise between complexity and storage space.

So you'll just have to lookup the screen one time, instead of once for each object. Am I making any sense?

That has been the idea from the start. I never gave that up.

I don't know how you do with your X, Y positions of the objects in these screens, you'll have to clarify that more.

I decided to group all the objects of the same screen into blocks just because they share a lot of things because of that, and by grouping them those similar attributes can be defined only once, for the whole block. By knowing that they all belong to the same screen, and knowing the coordinates of that screen, I'm saving 2 bytes from the declaration of each object, for example.

All objects are defined differently. Some will need just 2 bytes and other will need 8, it depends on their type. Different objects need different initialization parameters.

Thanks for trying Celius. But this is a complex thing, and I can't seem to express exactly what the problem is. And even if I was able to explain it all, hardly anyone would go through the trouble of trying to understand it, because that would also be too much work. So thanks for trying!

But it seems I'll have to figure this one out on my own. I'll clean up my own mess. It's not like I'm needing the objects right now anyway. I'll first get the scrolling working, then I'll worry about objects.

[Celius]

Well, I'm sorry I couldn't really be of much assistance, but I just have one thing to ask. Why would so many screens be without objects? I'd like to help find a solution to your problem; I know how much it sucks to be completely stumped on what to do. Are you saying the whole pointing to blank screens thing is a waste? If so, I kind of agree, but when you think about it, it kind of has to be done. You could maybe do compression if you have many blank screens in a row, but I don't know how many you're talking about...

Coincedentally enough, I just finished my scrolling engine, which I'm so happy about, because I can now use it on pretty much any game, as long as I use vertical mirroring. Now I need to start thinking about the level engine and what-not.

[tokumaru]

Well, I'm sorry I couldn't really be of much assistance

Don't worry. It's really hard getting into other people's heads to understand their projects!

Why would so many screens be without objects?

Take a look at some maps of Sonic levels. You'll see that levels that have a bit more height usually have large areas of nothing, places that the camera never visits. Those types of areas will never have objects.

I'd like to help find a solution to your problem; I know how much it sucks to be completely stumped on what to do.

It will come to me eventually. In the worst case I'll just waste those bytes when there are no objects.

Are you saying the whole pointing to blank screens thing is a waste? If so, I kind of agree, but when you think about it, it kind of has to be done.

Well, this is the simplest, most automatic way I could think of for the program to handle.

You could maybe do compression if you have many blank screens in a row, but I don't know how many you're talking about...

Compression would help, yes. But I'm doing things a bit differently and not copying/decompressing the level maps to RAM (I have no extra RAM). It's all read from ROM, and all compression I'm using is based on indexing things of fixed sizes that repeat, a very specific type of compression that can be handled in real time.

Sounds like I'm trying to make it hard, huh? But seriously, don't worry. I'll work something out.

Coincedentally enough, I just finished my scrolling engine, which I'm so happy about, because I can now use it on pretty much any game, as long as I use vertical mirroring. Now I need to start thinking about the level engine and what-not.

Great! Let us see when you have something nice, OK? I guess my game is basically a level map with objects in it. Even the camera is like an object, one that is responsible for displaying the level map and the other objects. So my scrolling engine is actually the camera object. When I have it done, it's just a matter of programming all the other objects (including the player). But they are all just objects.

[tepples]

Most of the areas that the camera visits in the few maps that I looked at on that site have been contiguous top-to-bottom at any given x location.

For each 1-screen-wide column in your level, store a pointer to a column list. This column list contains a top screen number, a bottom screen number, and a list of pointers to screen object lists.

[Bregalad]

Personally I did it the way where I just say the number of object per screen ($0 to $8 are valid, $0 indicating no objects, and $8 8 objetcs, the maximum allowed per screen in my engine). Then each object has it's X, Y position beyond the screen and object type defined. However a radical difference is that I only load one screen at the same time (like Zelda and Final Fantasy Adventure).
If I were to dynamicly scroll between sceens, I'd have all positions of all objects being internally stored to something like 9 bits (where the upper bits of all objects could be packed a weird way to save RAM if needed), and where 4 screens are loaded at the same time. When scrolling to the right, the screen 0 will be reatributed to screen 2 and so on. In fact you could even have all objects position 16-bit in memory (where the upper bit means the screeen number in the considered axis (since there is two "dynamic" screens per axis), 8 bits for the pixel position beyond this screen and 7 more bits for fractional position, very usefull for smooth movement. Only bits 7 to 14 would be directly loaded when a screen is loaded, the 7 lower bits would be automatically reseted and the last bit either cleared or set in function on how the screen is internally loaded.

[Zepper]

It remembers Rockman game structure...

[tokumaru]

It remembers Rockman game structure...

The rockman series has a somewhat simple type of scrolling... it's either vertical or horizontal, not both at the same time. This means that the transition is always from one screen to another, which makes the scrolling engine and object placement much easier.

But in games that scroll in both directions, the camera usually has to "see" 4 screens at a time, as Bregalad said. And these screens must be easily located on the level map, which is much harder in 2-D than in 1-D.

tepples, your suggestion did give me some good ideas! I don't know if I'd go as far as assuming that there will always be a single contiguous section in a column of screens that contain objects, but the idea of having pointers for each column is very good.

I could probably have these pointers point to a list that contains the Y coordinates of screens in that column (since we came from a column, we already know X), and pointers to where the objects actually are. That way I would just have to search for the Y coordinate in the list, something I'm sure can be optimized somehow.

That'd be similar to storing a separate list of object blocks sorted by X and then by Y coordinate (like I said before), but by having a pointer for each column you can skip the search for X, and go directly to the search for Y.

I'll give it some more thinking, but indexing the objects based on columns or rows of screens does seem like a good place to start.

[Zepper]

Rockman 1 has the nearest model you have described, as using screens IDs to build up a level. The enemies uses a screen ID to be placed too. Things have changed completly in Rockman 2, and yet much more ahead (3,4,5 and 6).

Well, perhaps you should disassemble that Sonic pirated version for NES, named "Somari".

[tokumaru]

Well, perhaps you should disassemble that Sonic pirated version for NES, named "Somari".

I've researched some of Somari and Jurassic Boy, as well as the original Mega Drive games. The NES pirates do many things very inefficiently, and you can see that from the constant slowdown both games suffer from.

In the original sonic games, there is just a long list of object definitions, sorted by X and then Y coordinates. As the screen scrolls horizontally, all objects with a close enough X coordinate are checked, and if the Y coordinate is also close enough, they are loaded.

With extra RAM in the cart I could probably do it like this. Just a long list, and it wouldn't even have to be sorted, as I could sort it twice when the level loads, making one list sorted by X coordinate and the other sorted by Y coordinate, and store both in RAM. That way, locating the objects of any screen should be pretty easy. I'd probably have to dedicate a good 1 or 2KB of RAM for this.

Enemy placement in Jurassic boy is just terrible. Dead enemies come back to life with very little scrolling of the camera. Somari handles them much better, but I admit I haven't dicovered how it handles them yet, maybe I should take a look.

I know it also handles the level map in the form of screens, but since they are not compressed, there seem to be only about 32 of them per level.