Month: December 2019

A* Pathfinding: Debugging Special Cases

digm520admin / / A*, AI, Debug, Pathfinding, Programming
December 19, 2019

A* Pathfinding

Debugging Special Cases

ISSUES

Getting an Index Out of Bounds Error in EnemyBasicMovement Script

Error happening on this line:

Vector3 direction = (path.lookPoints[0] – transform.position).normalized;

Suggests that the very first point in a path does not exist, so somehow empty paths are being passed through the system.

Test 1: Increase A* Grid Size to Cover Entire Play Area and Spawn Points

Some of the spawn points are a bit off of the normal play area, so I made sure to cover anywhere the units could possibly exist with the A* grid so they always had a node to latch onto (even though I believe the clamping should cover this error). This did not end up being the issue as the error persisted.

Test 2: Increase Size of Walkable Plane Over Entire Play Area

Similar to the logic of Test 1, I just wanted to make sure the nodes were not not being created because the units were missing some usual piece of information they would have to make them. Turns out this was not the issue either.

Test 3: Make Sure Target is Set Before Instantiating the Enemy

I thought maybe a path was being created before the unit had a target, which could make sense for creating a path with size 0. I did this by having the pathing script disabled initially, and making sure the spawner passed in the target information BEFORE it activated the script. The error continued though.

Test 4: Do Not Move the Target to See if Error Exists

It seemed like most spawns didn’t get errors if the player did not move, so I moved the one spawn that basically did not have to move to reach the player’s x position and tested what happened without the player moving (The X position counted as “very close” to the player at this time since I still had some of the issues with converting between 3D and 2D coordinates). There were no errors at all when not moving the target during the game.

DETERMINED ISSUE

Something about the paths updating later in the units’ lives was creating these size 0 paths.

Test 5: Is Spawning Causing the Issue

I was not sure if spawning the units was somehow causing the problems still, so I just placed 4 of the unit prefabs randomly about into the scene initially and stopped the spawners. This did not get rid of the error, and had the units return to moving in big circles still.

Further Info

This was giving me a lot of trouble, so I went back to following the path of logic to see why it would be producing these 0 count paths.

  • OnPathFound method in EnemyBasicMovement is being passed an empty array of Vector3[] waypoints
  • PathRequestManager class calls this method through its own FinishedProcessingPath method
  • OnPathFound is the method assigned to the callback Action for the PathRequest object
  • PathFindingHeap is creating an empty waypoints array somehow

The zero count path is being created in PathFindingHeap somehow. This should be impossible as every path should at the very least have the start node and the target node, which would be a count of 2.

    Within PathFindingHeap

  • RetracePath takes in a startNode and endNode to create the entire path of nodes between them
  • In the problem case, a new path has been created when the target is only a single node away from the pathfinding unit’s current position
  • there is a while loop that runs until it hits the startNode, so in this case, it only runs a single time (since the only nodes are the startNode and the endNode), creating a single waypoint
  • this creates a path with a count of 1
  • then the SimplifyPath method takes in this path
  • SimplifyPath creates a new List of Vector3 to fill with only necessary waypoints
  • it does this by taking points from the passed in path, but it looks through this with a for loop which starts at i = 1 and ends at i < path.Count, because it needs a previous point to compare to since it is doing a directional check
  • since the path.Count is only 1 here, the for loop never runs, and we return an empty set of waypoints
  • Can possibly solve with a special case since a path of 1 node is also a most simplified case

Test 6: Add Case In Simplify Path to Deal with Receiving One Node

I just added a check case before the normal logic that if the input path for SimplifyPath was only 1 node, it would just use that node as the path. This reduces the number of errors significantly, but there are cases where even the base path passed into SimplifyPath has 0 nodes.

DETERMINED ISSUE

The PathFindingHeap RetracePath method is creating paths with 0 nodes when Unit is close to target. As a result, SimplifyPath also makes 0 count paths. The only way this can be the case is if the startNode == endNode, so this must be happening when a new path is being created even though the unit and its target are already considered to be on the same node. This leads me to believe it is an issue with the difference between the node size and the distance the target has to move before looking for a new path (pathUpdateMoveThreshold in EnemyBasicMovement).

Test 7: Reduce NodeRadius to Half (or Less) of Update Path Threshold

Originally the values for pathUpdateMoveThreshold and the nodeRadius were both 0.5, which lead to a overall node size (nodeDiamater) of 1.0. I reduced the nodeRadius to 0.25 (which gives them a total nodeDiameter of 0.5), so this was at or below the threshold.

SOLVED

This completely removed the errors from happening (I add mostly because I am unsure if there exists a case where having the nodeDiameter exactly equal the threshold could cause an error).

SUMMARY

There was a lot of going back and forth to figure out where this error was coming from, and it was even harder since I was having some other issues since I had not fully converted the 3D system to the 2D system. As far as I can tell, this should cover most of the strange cases the pathing should run into even with an updating target (which should mostly be extra for my purposes anyway). I should add a check between the node size and the update threshold to make sure that issue does not happen again.

A* Pathfinding: Edit for 2D

digm520admin / / A*, AI, Pathfinding, Programming, Unity
December 19, 2019

A* Pathfinding

2D Conversion

ISSUES

Pathing In Circles Away from Target

They move in a large circle around the entire game area. They go in a half circle consistenly then stop in about the same place everytime (either directly above or below the middle of the play area).

Test 1: Tone Values Down

I tried toning all their numbers down since my game area is relatively small in case they were just constantly over shooting node targets, but this did not change the behavior.

I think the direction I am aiming and moving them must be incorrect with how I changed the Vector math from 3D to 2D.

DETERMINED ISSUE

They can only respond to the player’s X position. If the player moves, the properly oriented ones will move slightly to keep at the same X value, whereas those facing the other direction will travel in a large circle to reach the same X value (since I guess they cannot rotate very easily).

Test 2: Edit Rotation Calculation

I just needed to remove an extra (-90) that was being applied to the rotation vectors for aiming them at the target. This completely fixed the issue for their initial movement, but they only move in the x direction after that initial reaching of the target now.

DETERMINED ISSUE

The target position is not changing its Y value for some reason, only its X value.

Next Steps

Either their rotation is messed up (so moving right only moves them along x axis) or the overall translation is messed up and is only moving them left and right. It could be another z/y conversion error somewhere.

Test 3: Change NodeFromWorldPoint Method to Use worldPosition.y instead of z

It looks like PathFindingHeap was using AGrid NodeFromWorldPoint function to determine the proper node from world points, but this was using the z value of the Vector3 input as to determine the y coordinate in the overall grid. This is why it was constantly hovering at the same low Y value, because those were the nodes that correlated with a z input of 0.

SOLVED

These combined edits fixed the pathfinding logic completely. They now constantly followed the target position properly and it updated accordingly.

How Command & Conquer: Tiberian Sun Solved Pathfinding: War Stories: Ars Technica

digm520admin / / AI, GameDesign, Informative, Pathfinding
December 18, 2019

War Stories

How Command & Conquer: Tiberian Sun Solved Pathfinding

How Command & Conquer: Tiberian Sun Solved Pathfinding | War Stories | Ars Technica

Link – Video

By: Ars Technica


Working on Pathfinding

Pathfinding, especially in a dynamic sense, is still a relatively expensive process to run. This is much more so when you are trying to apply it to a lot of units.

Tiberian Sun was running into a lot of issues they called “Artificial Idiocy”, which is when your AI just does really dumb stuff. Really illogical AI from a player’s game units very quickly make the player mad and aggitated. They say “If you spend more time making sure it doesn’t do something stupid, it will actually look pretty smart”. And to follow up, they didn’t need perfect pathfinding, they just needed “not stupid” pathfinding.

Some of their fixes included not accounting for the collision of other friendly units selected to move and wiggling stationary friendly units when encountered by moving friendly units. Not accounting for other selected friendly units made sense since most likely they would also be going to about the same place and would generally be out of each others’ ways. The wiggling was added as very simple to execute logic in hopes that it would “unlock” a path previously obstructed by the stationary units.

SUMMARY

This was just a cool video I stumbled upon pretty randomly. It was very interesting to see some of the “behind the scenes” for one of my first favorite computer games to play a long time ago. There are just so many things you take for granted that took a lot of hard work and were almost revolutionary for their time.

It is also interesting to see that some problems still exist to a degree, like the prcoessing intensity of dynamic pathfinding. I think my research in pathfinding recently is what brought this video recommendation to me on Youtube, so I have at least had a small taste of the pains they went through developing that. I also really like their thoughts on just minimizing the terrible choices of AI instead of maximizing its “smart” moments to make it nicer to work with and really look smarter in the end.

Unity Event Systems: Introductory Research

digm520admin / / C#, Events, EventSystem, Programming, Tutorial, Unity
December 17, 2019

Unity Event Systems

Basics, Setup, and Tutorials

ADDENDUM: An EVEN MORE AWESOME Event System, by viewers!

Link – Tutorial 1

By: quill18creates


C# Events

Link – Tutorial 2

By: Jonathan Weinberger {ON Unity Learn Premium}


Tutorial 1

They created a public abstract class, Event, that all types of events will just inherit from. This helps keep all your events nice and similar, as well as making sure they all have key methods such as those necessary for registering and unregistering listeners. Since each event type is its own version of this base event, they can each hold a different collection of listeners, which makes sense since you only want certain behaviors to happen when certain events happen (such as a unit dying).

Inheritance and Static Fields in C#

This was an interesting interaction that I did not know it worked this way. When a base class in C# contains a static field, and then you create a new class that inherits from this class, it actually creates its own separate and unique version of that static field (as opposed to their just being one overall static field contained in the base class for all classes that inherit it). This has pros and cons. The pros are that it is helpful when you want the derived classes to be able to hold data only amongst themselves. The cons are obviously that you will have to do something a bit extra if you want something to contain all the information from all derived classes from that original base class.

Tutorial 2

This is just a very basic intro to events in C# I found on Unity Learn premium. This was beneficial to just cover some basic rules of events in general again.

General Events Notes

  • allow us to create broadcast system so other objects can subscribe/unsubscribe
  • need delegate type
  • will cause an error if it’s null when called
  • helps classes be self contained (since they do not rely on communication directly with another object)
  • every instance of an object that wants to be subscribed to the event must make sure that it itself subscribes
  • have inherent security (as opposed to delegates)
  • General Rule: always have an unsubscribe for every subscribe

Final Notes

Unity Learn actually has a ton of information, tutorials, and practice for learning about events, so I will most likely look to follow some of them in the future. They range from a few more really basic ones such as the one I just checked out, to more challenging ones, and even advanced ones that are much more project based as well. I really think this type of system will be useful for my current personal project, so I want to understand it well in an effort to properly utilize it.

Sebastian Lague A* Tutorial Series – Threading – Pt. 10

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
December 16, 2019

A* Tutorial Series

A* Pathfinding (E10: threading)

A* Pathfinding (E10: threading)

Link – Tutorial

By: Sebastian Lague


Intro:

This tutorial gets into the idea of threading to help relieve some of the burden on processing caused by the pathfinding logic. Threading is not something I understand very well, so I will have to look into this more in the future, but I wanted to cover this tutorial just for completions sake.

Tutorial

This setup usese another namespace, the System.Threading namespace. This lets them use the ThreadStart delegate type and the lock keyword. ThreadStart can be assigned the value of some other delegate, with in this case contained the FindPath method from PathfindingHeap. I then looked up the lock keyword here:

https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/lock-statement

While this sort of threading setup has some unique syntax, it is an otherwise simple setup. There is a queue of PathResults that are just checked paths that are waiting to be called for the movement of units. The paths get created and checked to make sure they can hit the target, and once this is satisfied, it gets added to the queue.

Summary

I would need to have a better understanding of threading and how to utilize it to assess how useful this tutorial really was. I know the general idea behind it is to help distribute the processing load, but I do not know how well this new setup accomplishes that.

HFFWS Generate Scenario As Gameobject Hierarchy

digm520admin / / HFFWS, Programming, Thesis, Unity
December 15, 2019

HFFWS Generation System

Scenario Gameobject Hierarchy

Connecting the System for Scenario Gameobject Hierarchy Organization

To help with organization of the overall system in Unity, I wanted each generated scenario to be fully contained within its own, single gameobject hierarchy. To do this, I had the DemoManager, my highest level in the system, create an overall gameobject that will act as the parent for the entire scenario hieararchy. This reference was then passed to the current ScenarioManager object, which can then pass it to all of its associated Create classes so they can all instantiate their chosen objects as children of that same parent gameobject.

The other benefit of this is that it helps with spacing out the individual scenarios for my DemoManager. The instantiated empty parent gameobjects have their transform.position set by the spacingBetweenScenarios variable within the DemoManager. This gives everything childed to it some significant spacing to work with with minimal programming effort.

Each ScenarioSpecific# GameObject Contains a full Pulley Setup

Coroutine Error Investigation in A* Tutorial Series – Path Smoothing – E09

digm520admin / / A*, AI, Debug, Pathfinding, Programming, Unity
December 13, 2019

A* Tutorial Series

A* Pathfinding (E09: path smoothing 2/2)

A* Pathfinding (E09: path smoothing 2/2)

Link – Tutorial

By: Sebastian Lague


Intro

I wanted to further my investigation on the issue I had with coroutines when dealing with updating the pathing of the A* units when following the A* tutorial series, specifically in episode 9. I have included the sections “Error with Updating Path” and “Fix for: Error with Updating Path” from my last post to keep them together, along with my updates for the investigation.

Error with Updating Path

For some reason my version was not working properly. The path was updating fine, as I could see with the visualization, but the unit would stop moving and never move toward the target again. I was getting an index out of bounds error, some I have some issue with one of my arrays somewhere, but not sure where. It was running fine in the tutorial, so I must have missed something.

Fix for: Error with Updating Path

I have no idea how this works, but I saw it in the comments of the tutorial. For some reason, in the OnPathFound method in the Unit class, if you pass the IEnumerator FollowPath into the StopCoroutine and StartCoroutine methods as “FollowPath” instead of FollowPath() or using an IEnumerator variable, the updating works.

I think it may have to do with how coroutines are handled in Unity. My guess is that the quotations form is the only one that is properly stopping the correct “FollowPath” coroutine and then starting a new one. The other approaches might not be stopping it properly, which is leading to a weird issue where the coroutines are stacking on top of each other.

My other guess is that somehow these other techniques stop the coroutine but keep track of where it is stopped, and then start back up where they started. This could possibly be what is leading to an index out of bounds issue since a value might not be updated as it should after changing the path.

Testing

The issue is that using StartCoroutine(“FollowPath”) and StopCoroutine(“FollowPath”) works completely fine, but replacing “FollowPath” with FollowPath() or followPathRoutine = FollowPath() does not work. There is some functional difference between these ways of referencing coroutines that I do not see. For matters of testing, I am trying to see if I can get the variable reference method to work (followPathRoutine = FollowPath()).

Test 1

The error was pointing to this line specifically:

while (path.turnBoundaries[pathIndex].HasCrossedLine(position2D))

So this line does make sense for a possible out of bounds index error when looking in the turnBoundaries array. My first test was to check what the pathIndex value is right before this while loop executes to see if it was being passed a weird value at some point. It turned out that I never got a weird pathIndex value when the error occurred (upon moving the target), so the pathIndex was not being changed or anything.

This was actually a bigger issue than I thought because pathIndex is specifically set to 0 at the beginning of this coroutine where this line is located, which indicates to me that the coroutine is not properly being terminated and reset. This supported my thought that maybe the coroutine was resuming immediately within the while loop. However, a more logical issue may be that the path is being updated, but not the pathIndex, so this new path has a different turnBoundaries array where that same pathIndex (since it isn’t properly being reset) gets an out of bounds error.

Test 2

I followed this test up with another quick debug log just outside of the entire while loop containing this while loop (so basically at the initialization of this coroutine) just to see if the coroutine was being executed more than once at all. As I expected, it was not even being restarted at any point while hitting this issue. Since the error is within the coroutine and happening when a new one should be started (but clearly isn’t), this made it fairly obvious something was wrong with how the coroutines were being stopped and started.

Test 3

I decided to split up the functionality to see if I could isolate the issue better. I simply added in an Update method to StopCoroutine when space was pressed to see specifically what just doing that would result in. I started the game and pressing space did indeed stop the unit from moving. I then furthered this test by moving the target now, knowing for sure that the coroutine had been stopped. This did allow the unit to reacquire the target and start moving towards it again. However, if I moved it several times, the error would come back again.

It is also very important to note that pressing space bar again when the unit was moving towards the newly acquired target did NOT stop it anymore. This suggests to me that my coroutine variable lost reference to the specific instance responsible for moving the unit. This would also make sense with the issues that I was having since it tries to start and stop the same exact instance of the coroutine.

Furthermore, my debug log of the path index was still running during these tests, and I could see specifically that the pathIndex was NOT reset when it reacquired the new target and starting moving in this setup. So pressing space stopped the coroutine, stopping the unit, but when it started moving again, the index was not updated. It actually kept the same pathIndex it had before pressing space, but was using it to move still.

The main difference between how it normally runs, and the “press space to stop” version work is that it normally gets a new path, then stops and starts the coroutine, where as the other version stops the coroutine, THEN gets the new path, then starts another coroutine. This difference is allowing the unit to at least somewhat reacquire the target and move again.

Test 4

To more accurately match the case with pressing spacebar since that seemed to work a bit more consistently, I moved the StopCoroutine before updating the path variable. I then also added a debug check here to output what the current number of waypoints were every time the path was updated. This would help confirm the indexing issue since if the number of waypoints were lower that the current pathIndex that does not seem to be updating, it would be pretty clear that this is indeed the issue.

Sure enough this proved my suspicions. I could now move the target some without the pathing breaking, but once I hit a point where a path had less waypoints than the pathIndex, the error came up and it stopped moving. So in this case, the coroutine is clearly not being reset properly.

Test 5: FIX

Since my followRoutine IEnumerator variable seemed to be losing reference to the current coroutine I needed access to, I decided to try and reset it values each time I needed to run a new coroutine. After stopping the coroutine with StopCoroutine(followRoutine), I then set followRoutine = FollowPath() again, before calling StartCoroutine(followRoutine). This approach actually worked perfectly! It was now stopping the correct coroutine instance and creating an entirely new one when starting on its new path. The pathIndex was properly being reset to 0 as that coroutine was properly called from its beginning each time.

Summary

The first big thing is that the different input types for StartCoroutine and StopCoroutine actually act differently just from these inputs. That is very important to know moving forward with those. It also appears that this method of setting an IEnumerator variable can work in these types of cases by making sure to set it equal to the IEnumerator again. This must have something to do with how coroutines can have multiple instances of themselves running, so this helps specificy which instance of the coroutine to stop and start.

Sebastian Lague A* Tutorial Series – Path Smoothing – Pt. 08 and Pt. 09

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
December 13, 2019

A* Tutorial Series

A* Pathfinding (E08: path smoothing 1/2)

A* Pathfinding (E08: path smoothing 1/2)

Link – Tutorial 1

By: Sebastian Lague


A* Tutorial Series

A* Pathfinding (E09: path smoothing 2/2)

A* Pathfinding (E09: path smoothing 2/2)

Link – Tutorial 2

By: Sebastian Lague


A* Pathfinding (E08: path smoothing 1/2)

Intro:

These tutorials both covered the same general topic of smoothing the path of the unit.

Theory

Currently the units follow the path by making a straight line from one point to the next, which looks unnatural. To remedy this, they suggest a path smoothing technique.

This system starts with each point having a small line pointing directly to the previous point, whose length is called the “turn distance”. This line then has a perpendicular line emanating from the end, called the “turn boundary”. Once the unit passes this turn boundary, it will start to turn towards the next point in the path (instead of making direct contact with its current point destination). The only difference on any of the points is that the end point just has the turn boundary placed directly on itself (instead of at the turn distance). A turning speed value is also attributed to the unit to complete the parameters for controlling the amount of smoothing.

Turn Distance: distance away from a waypoint destination a pathing unit starts to turn towards the next waypoint in line

Turn Boundary: the actual line where the unit begins to turn towards its next destination

Programming

This was a very heavy math programming section that just had to do with drawing perpendicular lines accurately at a certain distance away from each waypoint along the path. To do so, they created a new struct named Line, and a new class named Path.

Line

This struct is responsible for all the heavy math behind building these lines perpendicular to the path properly. The names for the input parameters were misleading, as they named them “pointOnLine” and “pointPerpendicularToLine”, but the second is actually a point perpendicular to the perpendicular line it is making (so it’s actually just another point in line with the normal path line). It then uses these two points to build a line and figure out the line perpendicular to them, which is what is needed with this method.

This also deals with helping determine which side of the point the unit is approaching it from. This will be important for determining which way to start turning the unit to properly aim for the next waypoint.

Path

This class is mostly responsible for taking in the waypoints we have already determined and using those to position the turn boundaries. This just uses a directional vector between a waypoint and its next waypoint to position the turn boundary a bit before it (using the turn distance value). Then it just places Lines at these points.

A* Pathfinding (E09: path smoothing 2/2)

Intro

This follow up is to actually use what was created in smoothing the paths in the last video to actually have the unit move and follow this new pathing method.

Unit

This class was significantly modified, especially the FollowPath method, to work with the new pathing behavior. It was generally straight forward though, as it is still following waypoints for the most part. It just has additional behavior to start moving towards the next waypoint when it crosses a turn boundary.

Issues with Pathing System

There was an interesting part where they covered issues with very high speed units. Basically they could pass multiple waypoints in a single frame with high enough speeds, which can cause very weird behavior as it tries to come back to hit the next waypoint in its logic (even if it is now several waypoints ahead positionally).

They fixed this by changing the if statement for “crossing the line” to a while statement. This ensures that even at high speeds, it will stay within this loop of updating its waypoints until it reaches one that is has not crossed yet before changing its trajectory. It still behaves weirdly, but it at least reaches the destination very quickly, as it should.

Updating Path at Run Time

They basically just moved the PathRequestManager.RequestPath method into a coroutine. They added some conditions to update the path so it was not happening constantly. These were based on time and distance. The target needed to at least move a reasonable amount before updating, and a small amount of time needed to pass before each update. These were just to keep it from updating every single frame.

Error with Updating Path

For some reason my version was not working properly. The path was updating fine, as I could see with the visualization, but the unit would stop moving and never move toward the target again. I was getting an index out of bounds error, some I have some issue with one of my arrays somewhere, but not sure where. It was running fine in the tutorial, so I must have missed something.

Slowing Down the Unit Near the End

They wanted to add an extra feature where the unit slows down as it gets close to the end of its path. They added an extra method in the Line struct to find the distance between a point and the finish line (line going through the final point/destination). They wanted to use this to determine when to slow the unit down. This however has an issue with some paths where the finish line crosses through other parts of the path, as the unit would slow down at weird times.

To fix that, they used the stopping distance (the distance before the end to start slowing the unit) to go backwards from the end point to identify which waypoint the unit should start slowing down after. This was done by basically adding up the distance between each waypoint from the end backwards until that total distance was greater than the stopping distance.

Fix for: Error with Updating Path

I have no idea how this works, but I saw it in the comments of the tutorial. For some reason, in the OnPathFound method in the Unit class, if you pass the IEnumerator FollowPath into the StopCoroutine and StartCoroutine methods as “FollowPath” instead of FollowPath() or using an IEnumerator variable, the updating works.

This makes no sense to me, as it works completely fine the other ways when doing a single initial path, but as soon as you move the target and it tries to update, only one way works for some reason.

I think it may have to do with how coroutines are handled in Unity. My guess is that the quotations form is the only one that is properly stopping the correct “FollowPath” coroutine and then starting a new one. The other approaches might not be stopping it properly, which is leading to a weird issue where the coroutines are stacking on top of each other.

My other guess is that somehow these other techniques stop the coroutine but keep track of where it is stopped, and then start back up where they started. This could possibly be what is leading to an index out of bounds issue since a value might not be updated as it should after changing the path.

Overall Summary

There are a lot of interesting ideas going on here, and it will take some time parsing out the useful bits for myself. The path smoothing is definitely a nice touch to help keep the moving units from looking extremely robotic in their movements, and there are probably a lot of other ways to look into to achieve this as well.

Updating the paths at run time is a huge feature I would like to understand better and explore more as it may be very useful to me in some cases. I was having some weird trouble with they way they implemented it in this tutorial, so I would like to understand those issues or find another way to use such a feature.

Slowing the units down before they reach the end is not particularly useful to me, but this general concept of controlling the unit’s speed throughout its pathing could possibly be interesting. This will be something good to just keep in mind as an option.

HFFWS Scenario Building System

digm520admin / / HFFWS, Programming, Unity
December 12, 2019

HFFWS Generation System Design

Scenario and Create Class Interaction

Detail on Scenario-Create Interaction

My first pass on deciding on how to have the Scenario classes and Create classes interact uses the following flow:

  • Scenario holds all parameter ranges
  • Scenario picks random values within ranges
  • Scenario holds these values in various fields (read only)
  • Scenario calls overall creation method within each Create class
  • Scenario passes parameters to Create class through this Create method

The overall idea here is that the Scenario class can hold all the parameters necessary for all its Create classes, as well as the Inspector interface for setting the ranges for these parameters (so the designer can design the scenario from this single class object). As the Create classes determine their varied values within the sets of parameters, they can feed information back to the Scenario class to update how the other Create class parameter ranges are set. So if the variation chosen for a certain Create class does not work with certain values in another Create class anymore, that range will be updated to ensure all the Create classes work together properly no matter the values selected as it goes along.

Next Step

Create Scenario Gameobject Hierarchies

I want each generated scenario to be childed to an overall newly generated gameobject. Each scenario should create an empty gameobject overall that acts as the parent for each full, individual scenario. I am hoping the positioning of this object will also serve as an easy way to space out the various scenarios with the DemoManager. This will just help with overall organization when demoing the project in Unity.

Creating New Scenario Objects

Currently the system has a single instance of each ScenarioManager object that has its values updated to create a single scenario, then they get overwritten to make another scenario instance. It may make more sense to create a new instance of that ScenarioManager class everytime a scenario is created so that the data is conserved for me to check later. This will also make sense as I add seeding to the random generation as well.

Sebastian Lague A* Tutorial Series – Smooth Weights – Pt. 07

digm520admin / / A*, AI, Programming, Tutorial, TutorialList, Unity
December 10, 2019

A* Tutorial Series

Pt. 07 – Smooth Weights

A* Pathfinding (E07: smooth weights)

Link – Tutorial

By: Sebastian Lague


Intro:

This tutorial covers smoothing the movement penalty values out over an area, as opposed to the areas just directly being either one value or another. This will also be helpful for my uses as most cases when updating movement penalties in areas will not just want to update the single exact node where an important action happened. While that area should most likely have the largest impact on its weight, it will make sense to apply a light value change around that area as well. This seems to fit right in with smoothing or blending of weight values.

Theory

Box Blur: weight smoothing algorithm using averages of values within a kernel around a block in the grid

Kernel: a smaller grid sample within the overall grid; used here as the space to gather data from to create an average value with

The smoothing theory they look at is called Box Blur. In this case, each part of the grid represents an average value of the blocks around it. This smaller grid used for the averaging process is called a kernel. They intitially show this off by using a 3×3 kernel, which averages all 9 values in the kernel and places that value in another grid in the same relative location as the center of the kernel. This shows off the idea well, but they mention a more efficient way.

The more efficient way is to do a horizontal pass and a vertical pass separately. Representing the same overall 3×3 kernel as before, they start by doing the horizontal pass with a 1×3 sized kernel. This adds the 3 values in a row horizontally. This becomes more efficient because when they move to the next grid element, instead of searching for the next 3 elements, they simply keep tabs on the current sum and subtract the leftmost value (which is no longer in the kernel) and add the new rightmost value (which was just added to the kernel).

This is repeated over the entirety of the grid until they all received a horizontal pass (in all cases, values near edges of the grid are repeated if the kernel would go out of bounds). They then go through this new grid of summed horizontal values and do the same process, but vertically (so a 3×1 kernel). This gives the same exact resulting grid as the first method that averaged 9 values at once with the 3×3 kernels, but more efficiently.

AGrid

The approach here is actually pretty standard to what I would have guessed. They create 2 new grids with dimensions equal to the original pathing grid for each of the blurring passes, horizontal and vertical. They do the horizontal pass first, which grabs values from the original grid and sums them in kernels whose size is determined by the designer. The vertical pass then uses the values from the horizontal pass grid to create its own grid. These values are then passed in as the movement penalty values to the corresponding original grid nodes.

The key things to note were:

  • They wanted the kernel to always be an odd value so that it had a clear central location, so the input parameter of blursize was always multiplied by 2 and had 1 added for the kernel size. This mathematically ensures they are always working with an odd value.
  • To replicate the idea of “duplicating values at the boundaries outside of the grid” they used Mathf.Clamp when searching for grid elements to sum so that if it ever went out of bounds for a grid index, it used a clamped value at the edge instead (effectively grabbing the same value again in edge cases).
  • The core of the algorithm needs values to already exist, so there is some additional logic for the first pass just to make sure all the intial values are properly set first before the true process begins.

Visualization

This again is something I always like to learn more about, and this was exactly what I wanted with this type of system just to help truly see what is going on behind the scenes with all the pathfinding logic.

They did this in the way I would have approached it. As they set the penalty values, they have a simple check to figure out what the lowest and highest values in the whole grid are. They then use these values as the bounds for a Color.Lerp for the visualization between black and white. This gives the nodes a gray scale representing their cost, with black being the highest values, white the lowest, and shades of gray for the values between.

This did show an issue with the current code. The obstacles had a slight blur of lower penalties around them. This is because the code does not factor in penalty values for obstacle areas at all, so they currently have a penalty value of 0. This is generally not ideal.

Summary

This tutorial was again, a great step in the direction I am trying to take this A* pathfindin logic in for my project. Since I want to update the penalty values at real time based on events that take place within the grid, it will make sense to disperse some of that value updating out from the single node the events occur on.