WARNING: ESOTERIC, NON-LANGUAGE/PLATFORM-SPECIFIC GEEKERY AHEAD
So, it's no secret that I like to design games. Finishing those designs is a different story, but I do enjoy the process, and I'm always super excited when I start a new project.
I'm thinking right now of dynamic room detection in tile-based games. Sometimes, you want to do something to a "room", rather than to individual tiles. How do you get the game to recognize what is a room, and what's not?
I have semi-dynamic room detection in Ion Trail. As part of ship design, you place room control nodes in the upper left corner of the room, and it detects the dimensions of the room, and tells the tiles which room they're a part of. It has to be a rectangular room, but it makes layout much easier.
But what if you didn't have to do that? What if you wanted non-rectangular rooms? What if you wanted something where you could change the layout in-play? That's what I want to discuss here.
Now, the system I have for Ion Trail, the pre-placed Room Control Node (RCN) upon starting the game immediately tags the tile it's on, and then uses that tile to start a cascade process of pinging the other tiles. It cascades down and right, which is why the RCN has to be in the upper-left node. It prevents any sort of duplicate processes gumming up the works. The tiles identify adjacency, and whether the adjacent tiles are across a wall. If they're adjacent and not across the wall, they name themselves part of the triggering RCN's room, and return data which is used to calculate the height and width. It's a pretty elegant system, if I have to say so myself.
But it's utterly inflexible. While I could add the ability to place the RCN in-game, it would still require proper placement, and rectangular rooms.
Now, I've been playing Prison Architect lately, and they've got a neat solution; manual zoning. You create zones, which are also rectangular. The zones have the ability to detect adjacent zones, and consider themselves part of the same zone, which allows for non-rectangular zones in play. They can detect if the tile beneath them is valid (indoor outdoor) and whether or not specific items are within their boundaries. It's elegant, but not without issues of its own. Forget to manually designate a zone, and no matter how many showers and drains you've got, the game will completely ignore it. This is a feature as well as a drawback though, as it can allow you to dezone cells and cause prisoners to move to another part of the prison, and similar operations.
But I still want something more. The zoning is nice, but not universally applicable. I just want something that tells the game, and the player, that this is A ROOM.
I think the solution lies in the tiles themselves. Each tile is an object, and thus should have a unique identifier. These identifiers can be sequenced, which can allow for a hierarchy. This'll be important in a minute.
So, okay. How do tiles determine if they're part of a room? First off, I want to differentiate tiles from empty space. Empty space is still potentially part of the playable space, but is irrelevant for room detection. So, there's some triggering event. Maybe the creation of a tile, maybe periodically during the game, whenever. It triggers on a tile. That tile then looks in all directions for other tiles. If it finds a wall, it will ignore tiles on the other side of that wall. If it finds a tile that's not walled off, it activates the search process for that tile. If the tile is already searching, it will not try to reactivate the process. The initial tile will set it's object ID (oID) as the RCN. Then, whenever two tiles that are actively searching talk, they'll compare their oID to the current RCN. If a new tile's oID is lower than the current RCN, then the RCN will be changed to the lower (older) oID.
So there's this cascading process. Eventually, you'll have all of the tiles in a given area (walled off) in "search mode". How do they know when they're done? Maybe once a tile has activated search, it'll drop into a wait mode; during wait mode, the tile will compare its FCN value to the FCN value of it's FCN, which will keep updates moving toward the oldest value. When there are no more tiles in search mode and they're all in wait mode, they should all be pointing to the oldest oID object as the RCN. Here's the rub. They're all waiting, nothing is going on as the RCN isn't updating... But each individual tile only knows it's own state. The RCN doesn't actually know which tiles are part of the room, though the RCN and all of the other tiles know who's in charge.
Does the RCN keep some sort of matrix, to keep track of all of its tiles, and their states? This seems problematic, as each tile will have to have the potential to keep this matrix... and when does the matrix get updated? When the room search is complete? We still don't know how to tell the RCN that it's done. The matrix could tell it that, but that means that there'd end up being multiple matrices being generated during the room detection, which would mean that, when each tile updates its RCN, the matrices would have to be merged. It'd be unwieldy fast.
So, okay, back up. Maybe the RCN doesn't know which tiles are which? Say there's a value on the RCN called v_roomstat. A tile will look at this value, and compare it to its own status; If the tile's status is searching, and v_roomstat = searching, it'll do nothing. If they don't match, it'll update that status to match it's own. Which means every tile that is waiting will try to tell the RCN that the room is waiting, and every tile that is searching will try to tell the RCN that the room is searching. Eventually, they'll all agree, and the value will stop being changed. When the value has been "waiting" for a designated period, the RCN will know that no more tiles are searching.
This is problematic only in as much as there might be an issue with multiple change operations being pushed simultaneously. That'll depend on the platform that the program is running on. Since this is still a thought experiment, we'll assume it's not a problem right now, and move forward.
So, we've got a blind RCN and a bunch of tiles that know who the RCN is. This is somewhat useful, because a thing can happen to/on a tile, and the tile will be able to communicate to the RCN to tell what happened. But how do we do things to the room as a whole? That's the primary purpose. We can call on ALL tiles, and pass the RCN as a parameter, so only the tiles that point to that RCN will actually run the function, but I think that would use a bunch of resources unnecessarily, even if it's only for a blip of time, as each tile was like "Who, me? Oh, never mind." Maybe we go back to that matrix idea, again, except we only really need the oIDs of the tiles, so an array should work fine. So, the RCN, once all of the room tiles are done searching, turns them all off (so status is now idle) and now generates the matrix. We'll probably have to do the all call at this point, but only the one time per room detection, not every time we want to do something to the room.
But still, how do we populate the array? An array is a list of values. You access the items in the array by calling the array and the index of the item. Depending on the platform, you can possibly just create a dynamic array, and pop each tile onto the end of it as it reports in, but I don't think this solution is ideal. In Ion Trail, it was easily done because the RCN could just call an itemAtPosition function incrementing the x and y values through a a pair of for-loops, and pop them into place on a pre-generated array, since it already knew the number of tiles in the room. As this never changed, It was done once at the beginning of the game, and never again. Obviously that solution won't work here, since we've got to allow for non-rectangular rooms, and an unpredictable number of tiles.
I think it might be worthwhile to use a linked list, instead of an array, since it allows for dynamic changes a lot better. The RCN would be the head of the linked list. We already know it's the oldest tile in the room, so we can use the oIDs as a list, starting with the oID. Any older tiles would simply not be called. Incrementing the oID call, look for the RCN value. If the RCN value matches the room, then pop that tile onto the end of the linked list. Then, when you want to do something in the room, the RCN calls the function, then sends the order down the linked list, until it hits the tail, and terminates.
I think that's workable. I want to go home and try it now... I guess I'll let you know how it goes.
No comments:
Post a Comment