Player movement, levels, objects

Given the field of vision implementation from last time, I decided it was time to test it and make the game a bit interactive, by allowing the user control of a character. This has been really important, as it has forced me to focus on making level transitions, ensuring movement cost maps and visibility maps work ok, ensuring that save/load works correctly, and a myriad of small little things. Below are a few videos and a list of things done since the last blog post:

Animated and fuzzy fog of war
  • Better fog of war this time, implemented as a simple pixel shader. It’s simple, it’s fast, looks better and does the job for now. The video also shows from about here that now sprites flip horizontally when moving towards the other direction, while when moving vertically they preserve whatever direction they were facing. This costs 1 bit in the 128-bit data per moving sprite, not a big loss or cost 🙂
  • Added functionality for level movement costs (slightly different than overworld moving costs), consisting of background (walls/floor/liquids) and static objects.
  • A* and all other path calculators take into account that diagonal movement is only allowed when the related cardinal directions are passable.
  • Creatures have light sensitivity, and overworld and dungeons have light levels, that affect line of sight radius.
  • I wanted to refactor a bit of the territory system regarding propagation of influence by replacing the data per tile from class (reference type) to struct (value type), so that led to an exciting journey of more changes, fixes, bug discoveries and further bug fixes, and now it seems to be back on track, better, with less code and fewer bugs.
  • Field of vision optimisation that, when the player/sensor moves to an adjacent tile, we only clear the visible data from the surrounding circle with Los+1 radius, instead of clearing the entire map. This of course is not uncommon, but it also had to be done, as now the related performance cost went from 50ms to 0.2ms when the player moves in the overworld, because the refreshed tiles went from 512×512 to 20×20.
  • So far I wanted to have entity “configurations” which are objects that store the exact information to generate an entity, but decided against that due to the cases when entities have to reference other entities during the generation before the entities are created. So now, for example, when procedurally generating a lock and key, I have to create both entities, configure them, put the reference of the door needing the particular key entity to be unlocked, and then call the magic function “EntityBeginPlay” which makes the entity visible to the game, listeners, other entities etc.
  • Level objects (fountains, chests, etc) can now affect movement and visibility. Can now push level objects and update movement/visibility maps appropriately. Also, added doors, and can open and close them at will, blocking movement/visibility. Also, as a fun sanity check, when pushing a fountain in an open door, door can’t close.
  • Explored map disintegrates a bit when revisiting a level. Should later do it based on last visit time. Static objects disappear in explored areas when revisiting a map
  • Save/Load works from overworld and levels
  • Sparse 2D multimaps to store level objects and creatures
  • Ctrl+click moves character towards highlighted path, right click cancels path (this is for fast debugging, should later change with the introduction of turn system)
  • Slightly more flexible sprite rendering, with a list of animations and indices per animation type. So I have a “default”, “moving”, “death” etc animation types, and I can have for example “door closed” “door open” “door locked” as different animations per type.
  • Perlin noise precomputed inverse distribution function and cumulative distribution function. I wanted mainly the IDF, for cavern generation, as I wanted a scalar variable “density” to control how open or claustrophobic a cavern map is. I wanted density to vary in a linear way. My caverns are generated using thresholded perlin noise. But the perlin noise distribution is not uniform therefore the threshold value does not exhibit linear behaviour. Therefore IDF can be pre-calculated and used instead as density, as we feed it a probability value (that can be linear) and we get as output the threshold value to use. So, I did a test with this new variation, and for 10% density to 90% density the final map (after connectivity, etc) looks as follows:

White is open space. The maps get progressively more constrained in a linear way. The last map is very constrained, therefore a lot of parts have been discarded post-connectivity

Here’s a video showcasing:

  • Level transitions and overworld-level transitions
  • Fast-path traversal
  • Pushing objects
  • Opening-closing doors
  • Degradation of explored map after leaving level

Field of Vision

There are lots of FoV algorithms out there for roguelikes. Here’s a non-exhaustive listing, with several dead links and incomplete descriptions, and also here and here. So, why carefully search through everything and pick one, when you can make your own? I had an idea several years ago, that I finally managed to implement in C#, as that’s what I’m using now for the game.

The idea is very simple (and certainly not novel, as I’ve seen a few other similar examples around), and it’s based on:

  • Processing an ordered list of cells, sorted by distance to the viewer. This list, if represented relative to origin (0,0), it can be calculated once in the game
  • At every cell, we sample up to 2 previous cells towards the direction of the viewer, and based on relative angles (demonstrated below), we add their contributions together. Diagonals and straight lines sample just a single cell: the one before.
  • Visibility can decay with distance, for lighting as well as other purposes (e.g a creature at a low visibility area can appear as a question mark)
  • Grid cell visibility can be any value in [0,1], so partial blockers are possible

The percentage contributions from the previous cells are calculated based on the projection of the normalized vector to the longest axis:

X is at an offset of (-2,-4) from the viewer. Y is the major axis, as 4 > 2. Projection of the normalized offset is 0.894. Thus, contribution from A’s visibility is 89.4%, and from B is 10.6%

That’s it really. The visibility function is used up to twice per cell, so we can cache it as we go at some temporary storage. I’d be happy to put it in an existing testbed, but I haven’t found a nice, easy-to-run one in a language that I’m quite comfortable with (C++, Python, C#). I’m pretty happy with the results as it looks reasonable and should perform well.

Here’s a video of walking around the overworld where visibility is affected by elevation difference (we can see higher from a mountain, but we can see little past a mountain when we’re in the valley), humidity and vegetation density. Unfortunately, humidity and vegetation density are not very clearly represented with the current tiles, so the result might look slightly arbitrary:

Here are some test images with various test cases for the FoV algorithm, showing continuous visibility (for lighting) and binary (for fov tests). The green gradient is the visibility. Red is the viewer. Dark areas are walls.

And here are the same examples, but the walls obscure visibility by 50% only

Level Generation II: Sparsely distributed entities: entries, exits, treasure, etc.

A generated map with sparse elements: entries, exits, fountains, chests, keys, pressure plates and locked doors.

So far, we’ve generated the layout, which is a 2D array of bitmasks, where each tile stores a variety of useful information, e.g. if it’s floor or not, if it has liquid, if it’s a door, etc. This information is stored densely, as we always need to have such information about every tile.

In the next stage, we need to place things that appear sparsely on the level:

  • Level transitions (map border to exit wilderness, stairs)
  • Interactive objects: treasure chests, fountains, etc.
  • Puzzles and traps: this is a generalized group of a number of locations that have a relationship with each other, such as:
    • Locked door and key (1 tile + 1 tile)
    • Locked door and one or more pressure plates (1 tile + N tiles)
    • Pressure plate and dart trap (1 tile + 1 tile)
    • Pit trap (1 tile)
    • Secret bridge activated by pressure plate (1 tile + N tiles)

We run this sparse generator independently per generator area, so that when placing things, we know that the locations underneath are part of a common theme; for example complex dungeon-specific traps would only be placed in a “dungeon” generator area, rather than a cavernous area or a forest.

In order to place a generic “thing” on a map tile, we pick from a list of candidates, that all fulfill certain criteria. The code does exactly this: Each sparse element specifies a number of criteria, and then we process the map, gather candidates that fulfill those criteria and pick a random one. We repeat the process as many times as needed, re-calculating the criteria each time, as for example we might not want to place 2 fountains next to each other, so after every fountain is placed, we need to regenerate the candidate tiles. This process is repeated for everything below. Some always-on criteria are:

  • Tile must be floor/non-obstacle
  • Must match current generator id
  • No other sparse element on the tile, unless it allows overlapping

Part 1: In and Out

The first and most essential elements to place are the entries and exits to the level, as nothing should block any path. For outdoors maps, which are typically the outermost, encompassing generator (color-coded red here for example), we use all the floor tiles on the border that are not in liquid. Example of this is in the first image of this post, at the borders.

Depending on the map specification, we place zero or more exits (stairs up or down, gateways, anything) at particular generators. For the example that I’m using, I set “generate 3 exits in the innermost generator area” (color-coded blue)

Level entry/exit criteria:

  • On map border (for entries only)
  • Not in a tile with any type of liquid
  • Not on a door tile

After we generate the entries and exits, we calculate all paths from all entries to all exits (using dijkstra maps). We mark tiles on those paths and make the combined “hot path”, so we won’t accidentally create unsolvable levels (e.g. locking a door that lies in a path and placing the key behind it)

Part 2: Single-tile elements: Locks, keys, chests, fountains, etc

Each of these has their own criteria. Keeping things simple, here’s how it stands now:

Fountain criteria:

  • Not next to a wall (looking at 8-neighbourhood)
  • Not in any liquid
  • Not within a distance of 15 (euclidean) to another fountain
  • Not blocking passage (e.g. would not be placed in a single-tile-wide corridor)

Chest criteria:

  • Next to a wall (looking at 4-neighbourhood )
  • Not in any liquid
  • Not blocking passage (e.g. would not be placed in a single-tile-wide corridor)

Lockable door criteria:

  • Door tile that is an edge to the dungeon graph that leads to a leaf node (effectively, provides access to a single room) and is not part of the “hot path” (so we won’t lock a room with stairs)

Key criteria:

  • Not in any liquid
  • Not on a door tile
  • Not in the room that is locked
  • Not in the room next to the locked room (“Here’s the key, and here’s the door, congrats”)

Pressure plate criteria:

  • All “key criteria”
  • Within a distance of 15 (euclidean) to the associated mechanism (e.g. locked door)

The results of the above can be seen in the top image. The blue-laced doors are the locked doors with keys, and the green door is the door linked to the pressure plates (the grey-looking things).

We are not generating entities here, but just linking requests “generate some locked doors and keys for me according to these criteria” to results (a list of locations), as it’s up to later systems to materialize the entities.

Auto-explore and combining Dijkstra maps

The obvious thing to do after generating a map is to test it. And, what’s a better test than auto-explore? So, after adding quickly the recursive shadowcasting algorithm for fov, we create a very basic autoexplore bot:

The bot originally used the logic from here, where we mark all invisible tiles as goals. I did not like that for a few reasons:

  • Goals are invisible, so we can’t modify the weights with any intelligent and fair reasoning, as we don’t know what the tile is. For example, if I want to prioritize unexplored tiles of a different generator fairly, I can’t do that as I don’t know the generator id of the unknown goal tile.
  • For a large map, the number of goals starts as ludicrously high, which costs a lot of performance (and can cost memory as well). Gathering all the invisible tiles and setting them as goals in the dijkstra map could require tens of thousands of tiles.
  • We can’t necessarily go to the invisible tiles, so intuitively it does not make perfect sense

Alternative algorithm: Goals are visible floor tiles that are next to invisible tiles. This guarantees that the set of goals is never too large (unless the map is very, very weird) and is perfectly intuitive as you want to set as a goal a tile that you can go to and it’s next to area that you haven’t explored yet. Here’s some C# code that conditionally adds a tile into a list of goals for the dijkstra map:

if (visibilityMap[tile] != 0 && !autoExploreFullyVisibleTiles[tile])
{
    if(layout[tile].IsFloor == 1u)
    {
        bool hasNbUnknown = false;
        foreach (var nb2 in math.Shape.Nb8)
        {
            var pnb = nb2 + tile;
            if (visibilityMap.InBounds(pnb) && visibilityMap[pnb] == 0)
            {
                autoExploreActiveBorder.Add(tile);
                hasNbUnknown = true;
                break;
            }
        }
        if (!hasNbUnknown)
            autoExploreFullyVisibleTiles.Set(tile, true);
    }
}

This is run every time we move, and the dijkstra map is re-calculated if any change happens in the list of goals (autoExploreActiveBorder). So far so good, we have a working auto-explore.

Prioritizing areas

Say we want to find the temple of doom, deep within the caves of misery, in the woods of dismay. If we start at the woods and we find the entrance to the caves, and time is ticking, we don’t really want to explore the woods anymore. So, how do we do that without a hack? Easy, by modifying goal weights! Our starting generator is say 0, and our goal is “the further the better”, so higher generator ids are better. We can set custom goal weights for the dijkstra map, so our goal tiles in the previous area get varying weights: higher generators get a priority boost. This priority boost is applied to all goals of all dijkstra maps, so for example chests in more important areas are more important than chests in less important areas. Now, as you can imagine, the bot prefers to go deeper, where it will find the exit from this level, which is deep into the temple of doom.

Multiple dijkstra maps

Dijkstra maps are like tapas, they are great for sharing. We can make a dijkstra map for the level exits that can be used by any adventurer that comes to the level and tries to find the exit. This is part of the reason that we might needs several dijkstra maps, for example one for the auto-explore, one for the treasures (a sentry entity might want to collect treasure but patrol instead of explore), etc. So question becomes: how to combine the maps? After a lot of experimentation and failures to combine the maps by summing or multiplying them, I ended up with the following solution:

def combined_dijkstra( currentLocation, dijkstra_maps):
    bestCost = infinity
    bestLocation = currentLocation
    for dijkstra_map,desire_strength in dijkstra_maps:
        (new_location, cost_to_new_location) = get_lowest_cost_neighbour(dijkstra_map, currentLocation)
        cost_to_new_location = cost_to_new_location / desire_strength
        if cost_to_new_location < bestCost && new_location != currentLocation:
            bestLocation = new_location;
            bestCost = cost_to_new_location;
    return best_location

So effectively we sample all maps independently for the best candidate, and choose the lowest scoring one, after weighing them based on a “desire” factor (e.g. autoexplore is more important than treasure collecting)

This works like a charm, and causes no oscillations. So now we have a bot that can collect treasure while exploring, with the ultimate goal to find the stairs. For this, we have 3 dijkstra maps and their corresponding desires:

  • Explore. All visible tiles next to invisible ones. Weight: 1.0
  • Treasure. All known tiles containing treasure. Weight: 100.0
  • Stairs. All known exits from the level. Weight: 1000.0

Demo time! Here’s a video that shows the bot playing the same level, starting from different entry points:

You might notice the greediness of the bot, as it knows it looks for cavern and temple, but it sees some juicy chests outside, goes and picks them up, and heads back in 🙂

Level generation I: Layout

After a break working on other things (and playing games for research purposes 🙂 ), at about July I started working on level generation, as an exciting way back in to development. Exciting does not mean short, however, as I have certain expectations from the level generator to be quite capable and flexible, instead of just generating a “caves” level, a “dungeon” or a “forest”. As a result, 6 weeks later, I’m nowhere near done, but some parts now do work, and this is what this and following posts will be about.

Parts of level generation

Levels are not generated in a single pass; the process is split into the following (tentative) order:

  • Layout: Passable/impassable areas, rocks, trees, doors, water, open sea, etc. Where creatures can move.
  • Gateways: Staircases, etc. How to connect one level to another
  • Foreground objects: altars, fountains, bookshelves, tables, etc.
  • Traps, puzzles, secret doors
  • Creatures
  • Decoration: Grass, cobwebs, carpets, etc

The order, while not final, should reflect some form of logical dependent order, for example layout comes first, gateways need a layout, foreground objects need a layout and also need to avoid staircases, traps are based on layout and foreground objects, creatures need to be generated based on the dungeon layout and also need to be aware of traps and maybe foreground objects, and finally decoration is applied to layout but needs to know about other elements, such as gateways and foreground objects, that exist on the level.

Requirements and use-cases

Example levels should contain:

  • Building interiors ( manor, guild hall, temple complex)
  • Buildings outdoors (village, ruins, cabin in the woods)
  • Outdoors environments (forest, desert, sea coast, and generally biome-themed areas)
  • Typical dungeon
  • Cave complex

Zones: The ${dungeon_type} in the ${biome_type}

One of the goals of the level generation system is to be able to utilise multiple generators for single level, so that level separation is not always artificial.

An example is the first level of a wizard tower in some location. The tower can be located in the swamp (don’t ask me how they built it, it’s probably not too structurally sound), in the snow, near the sea, in the desert etc. In order to add some sense of exploration, we want the player to wander a bit in the biome to find the tower. So, we need a biome-specific generator, depending on our location. When we find the building, instead of having some sort stairs to change to a different level, we can generate the first level of the tower embedded within the biome map. So you find the tower, open the door, get in and explore the ground floor of the tower, all in the same level. To achieve this, we need 2 different generators, the biome generator and a “wizard tower ground floor” generator, and embed the latter into the former and make sure the entrance is accessible and makes sense. The areas belonging to different generators will be called from now on zones.

Masks: Controlling the shape of zones

Instead of using simplistic rectangles to differentiate between areas, we can use some more freeform masks using noise and cleaning up the shape by removing islands, or even custom ones. As a result, we get zones like this:

Coastal map (red) with lighthouse (green)
Outdoors (red), mountain (green), dungeon (blue)
Outdoors (red), mountain (green), temple (blue)

Each zone uses its own generator, and we just need to make sure that the zones can be connected. Zones can be “open” or “closed”. Open zones are ones where the default location is passable, for example outdoors. Closed locations are ones where the default is impassable, such as caverns, dungeons, etc, as these are spaces carved into rock. We have to worry about connecting zones if at least one of them is closed.

Prefabs: Handcrafted areas in procedural levels

Procedural generation nice, but sometimes we want to place particular, handcrafted rooms and areas and mix them with procedural elements. Examples:

  • Boss lair: specially designed room, but we shouldn’t know where to find it
  • Fortress entry hall. If we enter the fortress we’re in that room, but we don’t know the rest of the layout
  • Fortress prison. It has a fixed layout, but we don’t know where it is.
  • Glade in the forest. We want a small area in the forest to have a very particular look (special placement of lake, trees, ruins), but we won’t know where to find it.

In the example images in this page, I use a small number of prefab rooms:

Entry hall: When I use this, it’s always the first room to be connected to a connecting zone, via the door on the top. The doors appear exactly at that location, and we won’t have any more doors.

Entry hall

Lair: When I use this, I ensure that it’s never connected to a different zone, so all doors lead somewhere in the same zone. The doors appear exactly at that location, and we won’t have any more doors.

Lair, in case it wasn’t clear

OpenArea: This is an example of an area that is open and has a few things in.

Open area

Not fancy, but serving as proof of concept.

Configurability

A very important part of the process is being able to configure the generator using simple data structs, loadable from configuration files (or dynamically created configurations). This “heterogeneous” generator was designed with that in mind, so that creating permutations is easy, although there are still quite a few parameters to set up. In this page I’m using 3 presets:

  • The dungeon under the mountain V1: An outdoors map, with a cavern system on the left side, that leads to a dungeon map
  • The dungeon under the mountain V2: An outdoors map, with a cavern system on the left side, that leads to a temple. The temple generator is different than the dungeon generator in V1, and uses a dragon-shaped mask, so that any rooms are forced to be confined in that shape
  • The lighthouse by the sea: An outdoors map, bordering with the sea, that contains the lower level of a lighthouse: a circular tiny “dungeon” which is effectively a few rooms (maybe even one) and a staircase. Players might or might not traverse water to get to the lighthouse.

Examples

Below are some examples, 10 per preset. Using basic tiles and minimal decoration, more on that in another post.

UPDATE: Here are some videos showing the process of generating the dungeons:

Porting to Unity IX: Overworld Props

This wraps up the overworld map graphics for now, as it did in the last series. Again I’m temporarily using HoMM 3 assets for demonstration purposes, but the concepts are generally applicable. The prop texture atlas contains subtextures that are multiples of 32, so I’ll call that a prop tile. E.g. some mountain ranges occupy 6×4 prop tiles, while a single tree stump would occupy 1×1 prop tile. The parts that have been changed since last time are steps 3 & 4: placement and rendering.

Procedural placement

Placement is done as a series of steps:

  • Place high mountains
  • Fill high mountains
  • Place mountains
  • Place vegetation
  • Place misc props

Placed props may overlap if this is supported (see composition group in above linked post). All of the steps follow a similar pattern:

  • Generate a step-specific set of candidate tiles to place the props
  • Select a step-specific subset of props to be placed
  • Run the placement process, checking composition groups, neighbour tiles, compatible biomes, etc

When we’ve placed everything, we do:

  • Sort from top-to-bottom of the map so that props in the foreground occlude props in the background (tiles further up/back).
  • Remove props that are completely covered by other props
  • Generate a 2D texture array that stores placement info (for each tile, which corresponding prop tile from the atlas we should be rendering)

Here are the results of the placement algorithm:

And here’s a super-resolution image of the map

Porting to Unity VII: Sprite rendering

It’s fun to run character simulations and generate results, it’s even more fun when you can actually see the characters. These past two weeks I’ve been writing the sprite rendering system, that doesn’t utilize gameobjects/monobehaviours, or unity spritesheets/texture atlases etc, it’s all homemade. So, how is it done?

Instancing

For sprite rendering, there’s no alternative, plain and simple. We have a very simple geometry (a quad), and we want to render N instances of it, each with its own parameters. The main parameters, for sprites, are:

  • Rect location in texture atlas
  • Number of animation frames (stored sequentially in atlas)
  • Current location in the world
  • Previous location in the world (moving sprites only)
  • Time at previous location in the world
    (moving sprites only)
  • Movement speed (moving sprites only)

From the above one can see that for moving sprites we need more data, actually it turns out to be twice as much. We can also reason that the list with the moving sprites needs to be updated far more often, due to the changing positions. Therefore, it makes sense to have two separated entity sprite lists, the static and the dynamic, each of which contains instance data that will be rendered with Unity’s DrawMeshInstancedIndirect function.

Entity sprite list maintenance

  • Entity enters map: add its default/idle animation to the static list
  • Entity exits map: remove animation from static and dynamic lists
  • Entity teleports: remove animation from dynamic list,
    add it’ default/idle animation to the static list
  • Entity moves to adjacent location: remove animation from static list, add its moving animation to the dynamic list
  • Every several frames, we go through the dynamic list and check if an animation has finished. If it has, we remove it from the list and add the entity’s default/idle animation to the static list

For the above, when we add an animation, we also set the instance data to a CPU buffer. When we render, the CPU buffer contents are copied to a GPU ComputeBuffer (if anything has changed), which is sampled in the shader

Here’s an example where every second, we schedule a movement to 10,000 entities. Runs pretty well except the last bullet point above, which I’ve disabled for this video. The video also shows an additional GUI sprite rendering layer with highlighted tiles (yellow squares) and the hovered tile is shown via a greenish sprite.

Porting to Unity VI: RPG elements, Time

This week I ported another bulk of data, namely RPG-system related stuff such as attributes, skills, skill categories, skill mastery levels and level-up strategies. The data all became scriptable objects (as they’re constant assets), and all except the level-up strategies were enum-ified as it is quite likely that in the code I’ll be referring to particular skills/attributes/etc (e.g. if skills[dexterity] > 10, do something)

I’ve added a much-needed global object with all the game configuration parameters (e.g. max character levels, skill points per level, etc), while in C++ it was pretty much a dictionary loaded from json to avoid recompiles, here I have it as a scriptable object with fixed fields, so access is faster, compiles fast and data are interchangeable.

Another addition is a very simplified form of date/time. I opt out of using C#’s DateTime or TimeSpan as they are for real-world time and therefore do not allow flexibility. What I’m using instead is a simple long value wrapped in a struct (called TimeUnit), representing microseconds. The struct stores loads of constants and helpers for printing and manipulating, so that in the end a TimeUnit is just an integral type with benefits. 64 bits support quite a bit of a range, so it should be enough for the game’s time system resolution.

Porting to Unity V: Danger!

Since last time, I’ve tackled (or not) a few issues.

NO gameobjects/monobehaviours in the game database / ECS.

First and more importantly, I’ve made the decision to represent entities with a custom, very lightweight class, that does not derive from any Unity stuff. Reason being that I don’t want to interact too much with Unity, especially derive from these classes that carry a lot of baggage. I’m pretty happy to manage entity lifetimes and bite the bullet in terms of inspector “niceties”, rather than start using GameObjects and then, when these are tangled deep in the game code, I realize that it’s actually a terrible idea and it gets too slow. So that’s that.

Entities are represented now with custom classes, and to avoid potential infinite serialization depth that Unity is not happy about, I use weak references. So, instead of:

city entity -> city component -> owned mines (entities) -> mine entity -> membership component -> owner entity -> city entity -> …

… which causes an infinite loop, I use the following:


city entity -> city component -> owned mines (entity references)

so the chain is broken there. The references are just IDs that look up in a pool. So that’s that. In the meantime, I’m trying to make the inspector show in place of the entity references the entity contents, but currently I’m not doing a good job. Revisit later.

Danger maps

This is simply the danger map calculation (what level of encounters one might find at a certain point on the overworld map), which involves distance field calculations to cities and routes and some poisson sampling, both of which I’m calculating in C++ via a native plugin. So, performance remains nice, which is nice. Here it is, alongside the biome/routes map. Red is dangerous, blue is safe

Visualizations

Implementing visualizers in Unity is a breeze, and I love being able to see what I hover over and see data, data, data. In terms of pixels or values in the inspector. I captured a video to show how this looks like, I love it 🙂

RPG

Last but not least, I ported the RPG-related datafiles (skills, attributes, skill masteries, etc). So, next work is going to be adventure location generation, and maybe character generation and levelling.

Porting to Unity IV: Pathfinding


Fairly straightforward work this week, porting pathfinding code from C++ to C#. The first two ports were of the basic low-level pathfinding functionality, namely A* on a grid (SearchGrid) and a graph (SearchGraph). This is the code shown in this post

The other ports were of the higher level wrappers that utilize both of the above. There’s a “basic” wrapper and an “overworld” wrapper. The basic wrapper is used as a reference to evaluate other wrappers and uses a dense grid, so it takes the longest but it would return the best results.

The overworld wrapper is the one in this post.

The performance currently, without any sort of profiling, is about 1ms per overworld path, in the Unity Editor where I’m working all the time. Compared to 0.22ms for Release/C++ and 3.37ms for Debug/C++ it’s not bad at all!