A* pathfinding with weighted tiles

June 30th, 2014 - 3:03 pm

Until now, NPCs in Hidden Asset didn’t care whether they walked on the road or sidewalk. When finding a path from one spot to another, they’d always choose the shortest path. But having NPCs walking in the middle of the road without a care in the world is pretty immersion-breaking. So I had to implement some kind of way of having NPCs prefer walking on the sidewalk. This turned out to be much simpler than I had anticipated.

A* pathfinding works by checking potential paths between nodes until the destination is reached. For each node, you store how far you’ve traveled to reach that node. When the destination is reached, you just backtrack through the nodes with the smallest ‘distance traveled’ value. This gives you the shortest path to the destination. For my purposes, each tile is a node.

The distance traveled can just be 1 for each tile. So if you move through 4 tiles to reach the destination, the distance traveled will of course be 4. But because the pathfinding will choose the shortest path, changing this 1 to some other value for specific tiles or situations can have huge effects on the final path found.

One example of this is that I don’t give the same value when moving diagonally as when moving straight. While moving straight results in the ‘distance traveled’ to be increased by 1, moving diagonally increases it by 1.4. This is quite simply because you’re moving further when moving diagonally across a tile that’s a rectangle than when you’re moving straight across it.

A Pascal code example:

IF MovingDirection IN Diagonal
THEN Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 14
ELSE Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 10;

This code snippet takes the ‘distance traveled’ value (G) of the current tile and applies it to the next tile while increasing it with either 14 or 10 depending on whether or not it’s a diagonal movement (I use 14 and 10 instead of 1.4 and 1 in order to stick to integers — the individual values don’t matter, they’re only important in relation to each other).

However, I can also say that moving across a road tile will increase the ‘distance traveled’ value by an additional 10. The result of this is that an NPC will only choose to move across a road tile if sticking to the sidewalk means that he’ll have to walk at least an extra 10 tiles. Furthermore, I can tell the pathfinding that if there’s a pedestrian crossing on the road tile, don’t add the road ‘penalty’ to the pathfinding.

So I add a function call to the above code. This function returns the ‘penalty value’ for a given tile.

IF MovingDirection IN Diagonal
THEN Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 14
ELSE Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 10;

IF WeightTiles THEN Tile[NextLayer, NextX, NextY].G := Tile[NextLayer, NextX, NextY].G + TilePathingWeight(NextLayer, NextX, NextY, MovingDirection IN Diagonal);

Note that I only add these tile ‘penalties’ if the pathfinding function was called with WeightTiles defined as TRUE. I don’t add this tile weighting when pathfinding for the player character, for example, as it should be up to the player to decide whether or not to use the sidewalk and pedestrian crossings.

The result of all this is that characters will stick to sidewalks and pedestrian crossings, but if they really need to cross the road and they’re far from a pedestrian crossing, they’ll still choose to cross the road instead of taking a long detour. Here’s my NPCs demonstrating safe traffic behavior (though they don’t care about red lights):

Click to enlarge

Another use for this would be to have characters walk around corpses instead of over them. If there’s a corpse on a tile, just add 100 (or some other large value) to that tile’s penalty.

New name, same game

June 23rd, 2014 - 10:32 am

This is something I’ve been considering doing for more than a year, and now I’ve finally decided to pull the trigger (pun intended). I’m changing the name of Hostile Takeover to Hidden Asset.

Hidden Asset logo

There are two primary reasons for this name change:

There’s a lot of stuff out there already called “Hostile Takeover”. The Syndicate co-op, a board game, sci-fi books, movies, etc. It’s a name that’s used for a lot of entertainment products, and as such it’s just too generic.

The name also poorly describes the actual game I’m making. I’ve had people think that it’s either a corporate strategy/RTS game or an all-out action game. It’s neither. It’s a stealth game with a focus on puzzle-like level design. Having a name that suggests a different game than the one I’m actually making probably isn’t a good idea.

The name Hidden Asset is a much better fit. It still suggests a game that has something to do with corporations and businesses, but instead of making you think of an action game, it makes you think of secrets and stealth… and conspiracies, which the game will have its fair share of.

The corporate assassins in-game are also referred to as hidden assets, so the name makes sense from that perspective as well. Finally, I’ve been able to find practically no other entertainment products with this name, so that’s definitely also a plus!

So there you have it. Hope you like the new name as much as I do!

New melee combat and weapons

June 16th, 2014 - 2:07 pm

One of the big issues with the previous releases was melee combat. It just wasn’t very intuitive. The way it worked was that you could hold down the right mouse button to block at any time, but if you held it down for too long, you’d start building up ‘melee fatigue’ and wouldn’t be able to neither block nor attack until the fatigue had expired.

This system was meant to keep the player from holding down the right mouse button to block continuously, but it just wasn’t very intuitive. Why, for example, would you build up melee fatigue just by holding up your arms to block a potential attack? It didn’t make much sense. So I’ve completely scrapped the idea of melee fatigue, and instead implemented a more classic system where you can only block when an actual attack is incoming. So now it’s much more a matter of being able to react quickly when your opponent makes a move. I also added Arkham Asylum-styled indicators above an opponent’s head to indicate when an attacking is imminent and you can block.

It also wasn’t clear when you could attack an opponent without risking your attack being blocked and you being stunned for a while. The way it worked was that your opponent would be stunned for a while after you’d blocked his attack, and you could freely attack him while he’s stunned without fearing him blocking your attack. It still works like this, but now I’ve added animation frames to show when a character is stunned and open to an attack.

Here’s a low-quality gif animation to show the new system:

And now I just noticed that the attack indicators should probably be red when you’re stunned… Adding that to my to-do list. :)

Melee combat is pretty simple and that’s on purpose, since combat really isn’t the main focus of the game. It’ll be a lot more about puzzling out situations and using your equipment to avoid combat. But there still needs to be a combat system for when your stealthing fails and there’s no other way out.

One way I’ll be adding a bit of depth to the melee combat system is through weapons. Different weapons can work differently and have different effects. For example, in the above gif, I’m using a knife. This weapon’s special characteristic is that it still does damage (to the opponent’s arms instead of head) when the attack is blocked. There’s also a baton that when used and blocked makes the blocked character stunned for a shorter amount of time. Other weapons can for example deal splash damage to adjacent opponents, or maybe you have to click the right mouse button fast to build up to a single deadly blow? There’s a bunch of possibilities.

Improved lighting technique

June 9th, 2014 - 1:31 pm

There have been a bunch of improvements to Hostile Takeover‘s visuals in the past year. I’ve upped the graphics from 24-bit to 32-bit, since it seemed more and more silly to sacrifice visuals for better performance on low-end computers. And I also abandoned the older, more retro UI in favor of a somewhat more modern and less obtrusive design.

But one of the changes that took the longest to implement was the new and improved lighting system. Not because it’s all that complex, but because it took some tinkering and experimentation to figure out how to do it right. So that’s what I want to talk about in this blog post.

In the below image, you can see the 3 levels of lighting quality that you can set in the game’s options menu. These 3 levels represent the lighting system as it has progressed since I first started working on the game. Instead of just using the highest quality in the game and scrapping the older versions of the system, I decided to allow players to set the lighting quality in the game, since on older computers, lowering the quality can improve frame rate slightly.

The 3 levels of lighting quality

The quality 1 lighting just considers the lighting level of a single tile. The floor sprites have the level of lighting of the tile they’re on, and the wall sprites the tile they’re facing.

With quality 2 (which is what was available in the old releases of the game), the lighting is smoothed between adjacent floor and wall sprites. To achieve this smoothed effect, I use vertex coloring. In OpenGL, vertices are basically the corners of the texture you’re drawing to screen. So when drawing a floor or wall sprite to screen, they’re drawn as rectangles (‘quads’ in OpenGL) and therefor each have 4 vertices:

A floor sprite A wall sprite

When drawing one of these sprites to screen, I can tell OpenGL how light or dark each corner of the sprite should be, and OpenGL then smoothes out the light level across the entire sprite and between the corners. To make adjacent floor and wall sprites blend more into each other, I set the light levels of the corners to be an average of the sprites that share that corner.

This works fairly well and certainly gives smoother lighting than for lighting quality 1. It’s not perfect, however, and as you can see in the comparison image, there are still some hard edges between the individual floor and wall sprites. The reason for this is that the corners of the actual floor and wall images don’t line up with the corners of the sprite. The floor is diamond shaped, while the texture is a rectangle. And because of the isometric perspective, the corners of the actual walls don’t line up with the corners of the sprites either. To fix this, I split the sprites into sub-sprites when drawing them to screen:

A floor sprite divided into sub-sprites A wall sprite divided into sub-sprites

This gives me sprite corners that line up with (some) of the floor and wall corners. And since the floor and wall corners now line up with the sprite’s corners, the vertex coloring makes the smooth lighting match up better between adjacent floors and walls. As a result, the transition between adjacent floors and walls is practically seamless. Here’s how the corners of a wall’s sub-sprites matches up perfectly with the corners of an adjacent wall’s sub-sprites:

Sub-sprite corners lining up perfectly

I’m really pleased with this system — not least because I’m now getting almost perfectly smooth lighting without any use of shaders or other more demanding methods.

It’s been a while…

June 2nd, 2014 - 12:20 pm

For the last year and change, I’ve been pretty quiet. This isn’t because I’ve stopped developing Hostile Takeover, though. To the contrary, the game has come a long way in the past year. I just felt that I needed to go into stealth mode for a while until the game was up to snuff again and ready to be shown to the world.

At first, I just wanted to fix a few things here and there, but then I kept finding new things that I wanted to fix or improve before I showed the game again, and all of the sudden, more than a year has passed. But now the game is nearing a point where I feel confident in sharing it with the world again, so without further ado, here are some screenshots:

Click to enlarge

Click to enlarge

Click to enlarge

Click to enlarge

As you can (hopefully) tell, a lot has changed since the last updates. I’ll go over some of the changes and improvements in future blog posts.

I’ve removed the download links to the old version, since it was terribly out of date and this new version isn’t yet at a state where it’s fit for release. Speaking of, I’ll most likely be doing closed testing for this and coming versions until the demo is done (which I’ll then probably release as part of a Kickstarter campaign). The demo will include three missions, with the first two being tutorials. The above screenshots are of the work-in-progress first tutorial mission.

Finally, I’ve set up a mailing list that you can subscribe to if you want to be sure to know about any game/demo releases or future Kickstarter campaigns.

And that’s all for now. Hostile Takeover is back! (Though it was technically never gone…)