All I do is code.

www.github.com/patrikpihlstrom

[patrikpihlstrom]

Pathfinding

Hello again,

Since my last post, I’ve been working on improving the AI. I’ve made some changes to the state machine. Namely, each state now has a substate that it can fully control and manipulate. This is useful for things like combat, where the NPC might want to be able to chase a player, and then start attacking said player when in range.

I’ve also implemented a pathfinding algorithm. Namely, A* (A-Star). The way it works is, it searches adjacent tiles, with some favoring while avoiding unwalkable tiles until the desired tile is reached. The algorithm uses two different lists of tiles in order to keep track of tiles that have been checked, and tiles that need to be checked. The inner-workings of the algorithm are as follows:

Calculate the F, G, and H costs for the source tile, and then add it to the open list. This list contains tiles that need to be checked. F = G+H H = The heuristic cost from the selected tile, to the destination tile. I'm using the euclidian distance as my heuristic. G = The movement cost from one tile, to another. Straight movement = 1, diagonal movement = sqrt(2)

Get the tile with the lowest F-cost from the open list, and add it to the closed list.

Check the tiles that are adjacent to the one just added to the closed list, and ignore any tiles that are either in the closed list, or unwalkable. If a tile is in the open list, recalculate the G-cost for said tile, and make the tile previously added to the closed list the parent of the tile in the open list. Obviously, recalculate the F-cost in the event of a parent swap.

repeat steps 2-3 until the destination tile is found.

[patrikpihlstrom]

AI

Since my last post, I've been working on familiarizing myself with the project, and building a Finite State Machine which will allow us to create smooth state-based AI. The way it works is, each NPC in the game has an FSM, which in turn has a current state, a global state, and a previous state. The current and global states get updated each tick, and the previous state is used in order to resume work if interrupted. For instance, if an NPC is patrolling, and gets interrupted by a player attacking it, it shouldn't have to start over from the first waypoint in the patrol route after it's done with it's current aggro state. Thus, we revert to the previous state.

Each state has an enter, execute, exit, and criteria function. All of which are voids, except the last, criteria function, which returns either true or false. Each state has a state that it transitions into, which is defined by the State Behavior. This allows us to create behaviors for different NPC types, that may act differently. For instance, one NPC type might want to transition into a stealth state after combat, while another might want to start patrolling. This allows for some unique and versatile AI with little effort after all of the states have been written, since a State Behavior simply defines the transitions themselves.

I made this image in order to aid any readers, as I'm rather bad at explaining systems:

[patrikpihlstrom]

Failing with Semi-Grace

I started this blog in order to document my learning, as well as the progress of a school project. I'm a developer in a team that consists of four other developers, and three artists. Our combined goal, in the long run, is to get a passing grade.

Our initial plan was to create a multiplayer voxel-based shooter. I know, right... It's a common mistake to be overly ambitious. Especially when working with a team of this magnitude, where you can easily take "well distributed workload", in the sense that people always know what to work on, and consistent communication for granted. The reason for the so called "failure", was in my opinion, a lack of motivation fueled by next to no visible progress. By the time we'd set out to have a playable version, we were nowhere near where we wanted to be. Everything was still a separate module, and there was still a lot of new systems that had to be written. We had a meeting where we sat down, and laid out the details of the project at it's state, took all of this into account, made a critical decision, and decided to scrap, or at least put the project on hold. It saddens me to have to part with this project, since I was quite invested in it. However, I'm glad to be able to start working on something more gameplay-oriented.

I feel like I've gained a lot of knowledge. Not just in the engineering department, but also in project management and teamwork. I'll do my best to stay focused and up-to-date with the rest of the team as much as possible, and I look forward to continue working with the same ambitious and talented people in the future. I hope that we can take this failure to heart, and make something beautiful together.

[patrikpihlstrom]

How to Take a Break

I haven't posted anything in quite a while... I've been working on trying to fix the same stupid bug for weeks now. It got to the point where I opened my text editor each morning, and just sat there without being able to pinpoint where the came from. Just a side note, spending your time like this isn't great for your mental well-being as a developer, and I highly recommend that you take a break if you reach this point. If you don't, you run a risk of just all of sudden not finding the things you love the most, dull. However, after my short break, I got back to coding. I re-wrote the code that handles the voxels' data to be cleaner. We're still stuck on the same bug, but now I'm slightly less insane.

Sorry for the short post, but I haven't really made any progress since my last post. I promise to keep you guys up-to-date!

[patrikpihlstrom]

No more Positions, and a few more Chunks

I'm going to go ahead and start this post exactly like I started my previous one.

Since my previous post, I've been working on:

Scaling down the overall memory usage of a voxel by removing the position, and replacing it with a function in the octree currently holding said voxel. This obviously meant that I had to rewrite a lot of my code, in order to manipulate voxels in any way. Among the changes lies a getPosition(index) function in the octree used to store the voxels. It looks something like this: x = (index%size%(size*size)); y = (index - x)/size%size; z = (index - x - size*y)/(size*size);

Finding new and exciting ways to divide the map =). Not really... Chunks are just convenient since they allow us to look at a set of voxels (at the moment 64*64*64), without having to worry about the rest of the map. They also allow us to easily send a certain set of voxels over the network. Basically, I moved the voxel octrees from the map object, to the chunk object, and created a vector of chunks within the map object. It's essentially just another layer of division. The most significant difference between a voxel octree, and a chunk is how a chunk stores it's position. It's just like a voxel in that regard. With an index, and a getPosition(index) function.

Bug fixing and optimizing(?)......... As expected, the mesher didn't like all of these changes, and I noticed a few bugs while I made said changes, and rewrote the mesher. Also, The division and distribution of voxels across child-trees is now faster, thanks to the lack of a position, since I had to figure out how to correctly distribute the voxels without checking for AABB-AABB intersection. By the way... Don't ever check for AABB-AABB intersection if you're going to populate an octree. Instead, iterate through all of the voxels for each eighth, and add them to their corresponding child-tree. for (x = 0, y = 0, z = 0; x < size/2; ++x)     for (y = 0, z = 0; y < size/2; ++y)         for (z = 0; z < size/2; ++z)             children[0]->voxels.push_back(getVoxel(x, y, z));

An image showing off the chunks:

[patrikpihlstrom]

Greedy Meshing and Refactoring

Greedy Meshing

Since my previous post, I've been working on actually compressing the amount of polygons needed in order to display the same amount of detail. This means that if we take a 1x4x4 configuration of voxels, where the voxels' positions in three-dimensional space is equal to the voxels' positions in the array configuration, we'll only end up with 6 quads or 12 triangles. This, of course being the minimal amount possible for the given configuration.

The algorithm I've implemented is called greedy meshing.

The way it works, or the way I've understood it, is that for each side (up, down, left, right, front, and of course, back) we need to get the visible voxels. After we have the visible voxels, we need to separate them by the axis defined by the direction currently being checked. After we've done that, we need to iterate through each voxel for each depth-level(relative to the current direction) and sweep said voxel.

The sweeping step is the tricky part in my opinion. Basically, if we're checking the direction "front", we'd first sweep by x, and then by y. This means that for each voxel, we need to check how far we can stretch the quad before we run into a voxel of a different type, or reach the edge of the map. First we get the width, and then we get the height depending on the width. This may not always yield the least amount of quads. However, I've found that sweeping in the reverse order is too expensive, and not worth the minimal performance gain post-meshing. A great illustration of the sweeping step can be found here.

Refactoring

After I implemented the meshing, I moved the voxels from a three-dimensional vector in the map class, to a one-dimensional vector in the voxel tree class. This didn't take too long, and didn't cause me too much grief, since the voxel tree class already contained a one-dimensional vector of voxel pointers. Most of the refactoring process was just searching for "voxels[i]->", and replacing it with "voxels[i]." (not really, but you get the point). This is just one of the things I changed during this refactoring process. But seeing as everything went smoothly I've decided to spare you the boring details, and cut right to the chase. Write module-like code and you'll have almost no trouble when/if you need to refactor parts of your code.

[patrikpihlstrom]

Voxel Trees, Meshes and Faces

This week (and the end of last week), I've been looking at quick and easy ways to mesh the world in order to give an as accurate rendition as possible, with as few polygons as possible.

My method:

I decided to utilize my voxel tree, since it provided a convenient division of the level of detail in the world.

One of the ways I take advantage of the voxel tree, is to create simple boxes where there is no difference in voxels, as opposed to creating individual boxes for each of the voxels that the voxel tree contains.

I have the images to back it up:

[patrikpihlstrom]

AABB-AABB and OBB

Lately, I've been working on collision detection between axis aligned bounding boxes.

The idea is that if the distance in x, y, and z from the center of one AABB to the center of another AABB is less than or equal to the (added dimension in a given axis)/2, then the two axis aligned bounding boxes intersect.

The way I resolve this collision, is by getting the volume of the third AABB created by the two intersecting ones.

glm::vec3(max(min(a.b.x, b.b.x) - max(a.a.x, b.a.x), 0), max(min(a.b.y, b.b.y) - max(a.a.y, b.a.y), 0), max(min(a.b.z, b.b.z) - max(a.a.z, b.a.z), 0));

When I have the volume, I check the width, height, and the depth and move one of the bounding boxes in the axis of the dimension with the lowest value.

This method will obviously not work for all objects. That's why the next thing I'll be looking at is OBB-OBB, and of course OBB-AABB collision.

[patrikpihlstrom]

This is the octree that will handle inconsistencies in the terrain. I've been working on it for a couple of days now, and I'm pretty happy with the way it turned out.

It recursively searches through the child-trees' voxels for each tree, and scans for differences in the terrain, then it splits said child into eight children. This process gets set in motion when a voxel is edited, by searching through the octree for the voxel in question and calling the function for the tree containing said voxel.

The first image is a failed attempt, which I found amusing.

[patrikpihlstrom]

Octree

I've just finished my implementation of an octree, which will be used in order to check for likely collisions in 3D space, among other things.