Author: SaltyJustice

What the hell is ray tracing, and what the hell is a blockmap?

Ray Tracing is the coding technique used to figure out what can be ‘seen’ from object to object. If you’ve ever played a first-person shooter, you’ve experienced a ray-tracer, because that’s how the game determines what parts of the map you can see and what parts you can’t. Objects in the foreground prevent you from seeing what’s behind them.

Ray Tracing is simply tracing a ray. A Ray is a geometry concept, it’s a line that starts from a point and travels in a direction until it hits something. In strict geometry, rays don’t hit things, but in our code they sure do.

Oh, and this would more accurately be called a ‘line-segment’ as opposed to a ‘ray’, because these have a definite end point. But since the code can be generalized to rays and ray sounds a lot cooler, I’m using ray.

Pandemonium uses ray tracing to figure out if an enemy can see you, the player. If the enemy can, they will chase you and trigger a battle. So it makes sense that they wouldn’t be able to see you through walls unless they have x-ray vision.

In this image, I have enabled Mei’s visibility cone to simplify things. The yellow area is what she can ‘see’ while the red polygon represents what she’d be able to see if the walls weren’t in the way. The red arrows are rays, and they collide with the blue lines which represent collisions.

Pandemonium does not simulate verticality. So, enemies cannot see over the water, because they can’t chase over the water. It’s one of those design decisions that makes a lot of sense from a gameplay perspective but not from a reality perspective.

Okay, so what’s a Blockmap?

Raytracing is computationally expensive. In order to see if a given ray impacts a line, we need to run the line-intercept function. It looks like this.

I sincerely hoped you enjoyed that link.

The line-intercept function must be run for every line in the entire map against every ray you want to trace. For Pandemonium, every viewcone is about 120 rays. You can customize the accuracy in the options menu if it causes slowdown. 120 is just a good middleground number that looks nice without being too intensive.

So, if there are 600 lines in a map, and 120 rays per viewcone, then that’s 72,000 calls of the line-intercept function for every entity with a viewcone. 600 is not an unreasonable number of lines, and some of the larger maps have thousands of lines. This gets expensive, quickly.

It sure would be handy if we had a way to only check a ray against the lines it could reasonably impact, as opposed to every line on the map. The rays are short and always focused around the same spot, so an optimization would mean instead of checking against 600 lines, we check against 10.

This optimization is called a Blockmap.

What does a Blockmap look like? How does it work?

Blockmaps simply sort the lines on the map by where they are.

Here we can see a crude overlay which shows what a blockmap might look like. The vertical lines are labelled ABC etc, while horizontal lines are 123 etc.

Block 1-1 contains lines A, B, C, D, 1, 5, and 6. Any line which touches the block at all is considered to be within it. This can be determined with a simple line-intercept function call, and only needs to be determined once. That is, I can compile this data into the map and it never needs to change. Block 1-1 always has the same set of lines in it.

There are 16 vertical lines and 16 horizontal lines visible in this image, give or take the edges. That’s a total of 32 lines. If I had a ray that started and ended in Block 1-1, then I would only need to check 7 lines.  That means the Blockmap speeds up raytracing by about 500%. Five times faster for a simple bucketing algorithm, pretty impressive!

If a ray starts in one block and ends in another block, all you have to do is check all the blocks it hits, which can again be determined via either a line-intercept function or a point comparison. Simply check which block the start point and end points are in, and check those blocks as well as any blocks between them. For a short ray like the one in this screenshot, a ray can be in as many as 3 blocks, which is still considerably faster than checking every single line on the map. The algorithm becomes faster the smaller the blocks are, up to the point where the blocks are so small that the algorithm spends too much time figuring out which blocks the ray touches and not enough checking line impacts. It’s up to the coder to figure out the optimal size, but in Pandemonium it’s about 3-4 tiles squared since the majority of collisions in the game are big square right-angles.

Bonus Optimization: Duplicate Line Check

When a blockmap gets really small, the same lines start to appear in many blocks. It’s theoretically possible for a line to be contained in dozens of blocks, though that doesn’t happen very often in Pandemonium. When iterating across the blockmaps, checking the same line twice is just a waste of speed. What do we do?

The blocks contain references to the lines, which are stored in a single master list. To prevent duplication, we can use a unique ID system.

Every time a ray begins a trace, increment a variable, called mRayPulse, by 1. Every line in the map likewise has a variable, mLastRayPulse, indicating the last pulse they were queried by. When a ray checks a line, set the line’s mLastRayPulse variable to mRayPulse. If the ray goes to check a line, and the line’s mLastRayPulse variable is already equal to mRayPulse, it was already checked and we can ignore it. Thus we avoid all duplicate line checks.

We can also optimize the algorithm a bit by shortening the ray after each impact. Finding an impact is not enough, we need to find the shortest impact, otherwise entities would still be able to sometimes see through walls. Each time the ray impacts a line, we shorten the ray. If a ray going from Block 3-3 to Block 1-1 gets hit in Block 2-2, there’s no need to continue checking Block 1-1 since it has already hit something in between. This doesn’t save much processor time but is certainly worth mentioning.

Can we optimize this more?

Yes! However, it probably isn’t necessary in this case. Blockmaps with a duplication-proof pulse checker are ideal for short rays, such as the kind used in Pandemonium. Rays that are very long, however, are a different species altogether and won’t work with a blockmap.

For very long rays, you need a tree sorting method. If you’ve ever played Doom, Quake, or Half-Life, you’ve played a game that uses one such method: Binary Space Partitioning. This is where all the lines in the level is split into two (hence the term binary) and the two halves of lines are then further split down recursively until all the lines are isolated. The more advanced methods, Quadtree and Octree, do this same technique but use a different splitter to break space into four or eight parts instead of two. The basic principle is the same, though.

A BSP has the advantage of being fast for an arbitrary set of lines and line lengths, while also not taking up much RAM. Blockmaps are very fast for short lines and take up a fairly large amount of RAM relative to their contents, but for long lines they tend to check way too many extra lines.

I will probably do a post on binary space partitioning in the future but for now, this post is long enough and got its point across.

And for all those of you who don’t care about blockmaps but made it to the end of the post anyway: Congratulations!

 

 

 

Yes, that’s right. Enhanced Mode. Check out this mockup I made. Yes I know the radar is totally wrong, it’s a mockup.

What is Enhanced Mode?

For those of you just joining us, Hop:Remastered originally started as a project to… remaster… House of Pandemonium. I think that’s obvious. But that job was completed after about 8 months of on-and-off work. Classic Mode is that, and it’s pretty close to the original but with more options and the bugs fixed.

Naturally, as soon as this job was complete, everyone wanted me to keep going. Add more features. Add new characters, new monsters, new stuff, new modes.

The scope got pretty big. There’s a lot I want to do with this, so much that it’d be so different from Classic Mode as to render them essentially different games. Hence, I started calling it Enhanced Mode.

Why are you making Adventure Mode first? Isn’t Enhanced Mode simpler?

Hey, this isn’t an FAQ.

But, yes, Enhanced Mode is simpler. But I want it to be more graphically interesting, and the creation of new characters and monsters requires art assets to match. So, the full development of Adventure Mode will also give me a full set of assets for Enhanced Mode, plus a much deeper lore and excuses to put in all kinds of extra features. Plus making Adventure Mode is a blast and so much fun you guys.

Let’s talk about the design choices.

Enhanced Mode is basically Classic Mode but with more monsters, features, ways to play, and other options. It is, in a word, enhanced.

When making such a thing, there are so many things you can do to improve the original that you essentially need to prioritize them. Identify what’s wrong with the previous version and fix it, and then add things to improve it. When doing this you must weigh them according to criteria. Here they are:

1. Accessibility. The more complex a feature is, the harder it is for players to wrap their heads around it. Keep it simple, stupid.
2. Cost to Benefit. The harder something is to implement, the more other stuff could get done instead. If something is really hard to code and has minimal payoff, skip it or redesign it.
3. Asset Cost. Sprites are pretty and line-art is superb, but it costs artist time. Text is cheap but doesn’t look as nice. Combine the two with an eye towards using the player’s imagination, but never skimp on art. Just get the maximum possible use out of it. Don’t make a pretty portrait and then use it for one tiny thing most players won’t even find.
4. Raw Fun. Once it’s in the game, test it. If it’s not fun (and you’re not making an art house game like Spec Ops or Papers Please), cut it or redesign it. Don’t put things in your game that aren’t fun.

Good designers are constantly taking shortcuts and doing little redesigns to get the most out of their limited time and asset budget. If you’ve played Adventure Mode, have you ever noticed how all the furniture in the game is on the northern wall of the building?

It’s not impossible to make furniture on the south wall, but then it’d be partially obscured by the high walls. This violates rules 1, 3, and 4 above. It’s more complex for the player for no real reason, it means I have to get my spriter to make twice as many tiles, and it certainly isn’t fun to guess if that’s a bookshelf or a foodshelf when I can’t see it because it’s facing the wrong way.

So with that, let’s take a look at some of my plans for Enhanced Mode.

Some of my plans for Enhanced Mode

Let’s start with the simpler stuff.

Armor, Weapons, Accessories

There’s a variety of new weapons available in the game with parallels from Adventure Mode. In the mockup, you can see that Christine is armed with an Electrospear, which is a powerful weapon that deals extra damage to robots and aquatic monsters.

Armor will also be in Enhanced Mode. Armor uses a degradation system. If you get hit while wearing armor, it takes the hit for you and loses HP. It breaks when its HP reaches 0. Some armor can be repaired, some regenerates HP over time, and some provides extra benefits like a defense bonus or speed bonus until it breaks.

You can also pick up accessories, like rings, amulets, and other bitties. These provide status boosts, with a chance to be cursed and have a malus or turn you into a Rusalka.

When playing as a monster, you can use weapons and armor. AI-controlled monsters typically spawn with theirs equipped already or use their bare hands and instead have higher stats. You can therefore help your allies by giving them your equipment if it’s better.

Levels and Statistics

That’s right, in Enhanced Mode, you can gain experience and level up. Your character gets stronger with each level, but groups of monsters can still take down a high-level character. The other humans on the field also level up, but the AI monsters don’t. It can therefore be a good idea to keep high-level humans… human. Because if they get transformed, they’re going to be very tough to take down.

Each of the six playable humans also has special abilities they learn as they level up. Each one thus plays differently. Sanya is very good at defeating high-health high-defense enemies with her powerful attacks, while Jeanne can learn to heal herself and summon weapons and armor for her teammates (and throw fireballs, but every mage does that).

Special Abilities

All monster forms come with special abilities, and there are more that can be learned in other ways. For example, all characters can learn magic spells if they find a scroll, though Jeanne’s are more powerful than the rest of the cast.

Special abilities usually cost Willpower or Stamina to use, though some are free. Most of them also have attached cooldowns where they cannot be used again for a few turns. Finally, some require combo-points which build up in combat and decay if there are no hostiles around for a few turns.

If you’re familiar with Adventure Mode, many of the special abilities are the same ones present there. Mei learns Rend to deal damage-over-time, while Alraunes can use Regrowth to recover their health.

Factionalism

Monsters are divided into a series of factions, based on their origins. These are (at present): Humans, Forest Creatures, Aquatic Creatures, Desert Creatures, Angels, Demons, Fey Creatures, Machines, Undead, and Eldritch Abominations.

The monsters are looking for recruits, and do not take kindly to other monster groups taking their catches. Different factions of monsters will fight amongst themselves for the human prizes, a fact which the humans can exploit. If you’re being pursued by some monsters, try fleeing towards other monsters of different factions.

Of course, when you become a monster you will be under similar pressures. They will attack you outright, sabotage your allies, and try to steal your equipment and human victims.

Each faction has several monsters that belong to it. For example, Alraunes, Slimes, Werecats, and Bees will work together as they are Forest Creature types.

Invasions and Bosses

Periodically, an ‘Invasion’ will be triggered. A portal will appear somewhere on the map and a group of monsters of the same faction will spawn out of it, along with a boss monster. The boss is a very tough monster, and is sometimes a named character from Adventure Mode. The portal will spawn reinforcements periodically as the monsters stream into the map, and the only way to shut the portal down is to deal with the boss monster guarding it. Of course, doing this will net you a lot of experience and possibly special items.

If you leave the portal too long, it will close on its own. This is bad, though, as the boss monster will then start wandering the mansion. Any allied monsters it finds will start to follow it in a retinue and they will probably curb-stomp anyone they find. Deal with the portal before this happens! Or, you know, don’t.

Faction Orders

You can set orders for your faction, which is very useful if you want everyone to group up. AIs of your faction will follow the set orders to the best of their ability. These orders include ordering your faction to group up with you, to spread out and search for targets, to stay together but periodically break off to look for loot (the AI will run to the group if they encounter a hostile), or to move to an exit point and leave the map.

Multiple Maps

Enhanced Mode has an option to allow you to leave the map and move to a new one. You cannot do this as a monster unless all humans have been cleared from the field. If you do this as a human, you will actually take control of another human on the field until they have all left the field for a new map. Most maps have one exit point, some have more.

Items spawn in logical places. You will often find armor and weapons in an armory, and potions in an alchemy lab. When playing with multiple maps, items will not respawn and instead will only spawn in new maps. Therefore, your team needs to move to new maps to keep finding new goodies. However, each time you leave the map, monsters will start spawning at higher levels. You’ll have to weigh the costs and benefits.

If you’re entering a new map as a monster, you will have to track down any escaped humans on the map. You may also keep a retinue of up to 3 other monsters with you as you go.

Victory Conditions

It’s now possible to actually win in Enhanced Mode! To do this, you must journey between several maps and locate six runestones. If you enter a map with a runestone, you will receive a notification and not be able to move to the next map without it.

The runestones have special properties attached to them, making them powerful items in their own right. They can also purify their associated human, turning them back into a human from a monster (each human has a color and symbol associated with them. Mei is grey, Sanya is red, Christine is violet, etc.). If you are on a map with a runestone but the bearer was transformed, they will spawn as a monster on that map and you’ll have to track them down once you find it. If the character gets transformed again, they will flee and you’ll have to find them, and their runestone, on a future map – assuming you make it that far.

If you become a monster, your goal is to track down and transform all remaining humans. After that, you ‘win’, and presumably go do monster things or open a pizza parlor or something.

That’s enough for now

I think I’ve rambled about Enhanced Mode enough for now.

I don’t intend to develop Enhanced Mode until we’re at least 2/3rds of the way through Adventure Mode, and it’ll be up to the Patrons to decide what my priorities are.

If you have good ideas for Enhanced Mode (that fit those four criteria above) and want to discuss it, we have a forum for that. Do that. I have a pretty long track record of implementing suggestions I get from patrons and forumgoers, so what have you got to lose?