Pedestrian pathfinding part 2: Collision detection

I spent much time during the last weeks in programming the pedestrian pathfinding. After investing much work into the buggy implementation of evasion pathfinding algorithm and many hours of debugging now it seems to work.

Instead of the vehicle implementation (using Dijkstra pathfinding) for the pedestrian I use a jumpoint-pathfinding and a grid map. 

To prevent pedestrians from colliding with aother pedestrian, they mark their map pos as blocked (drawn red in the screenshot).

To synchronize between the vehicles and the pedestrians the vehicles project their actual position onto the pedestrian map (drawn black in the the screenshot). So no pedestrian can enter a field, a vehicle is driving across. 

Only for exceptional cases (when the blocking of the map has not prevented a collision) there is a front collider attached to each pedestrian.

Pathfinding seems to work fine now. So I can now go on with a little more exciting part of game development including graphic stuff and game mechanics.

Decisions, Artificial Intelligence and Finite State Machines in Unity3D

After programming my first AI approach for the traffic system I've noticed that the reasons for the decisions of the vehicle are a little bit difficult to observe.

But for the future game I expect far more complex decision systems. So I needed a better debuggable solution than coding in normal C# methods.

After researching some hours I thought that “finite state machines” (FSM) could be a possible approach.

If found some implementations of FSM for Unity3D which were inspiring but not exactly what I needed:

So I decided to write my own finite state machine. It looks like this:

My FSM works by creating an instance of a state object for every available state.
Transitions from this state to the next state are attached to the state. 

For example:
The vehicle should follow another vehicle when touching it´s back bumper bar.
In this case the vehicle is running in the state “stateDrivingOnOthersBackBumperBar”.

As soon as no more touching the back bumper bar the state should be exited and the state “DrivingForward” should be entered.
So a transition “transitionNoMoreBackColliderTouched” has to be attached to the state. 

In code this looks like this:

// Create a new state for driving on others vehicle bumper bar
 stateDrivingOnOthersBackBumperBar = new StateDrivingOnOthersBackBumperBar(this); // Define the reason to activate to transition to change to state "DrivingForward" FsmTransition.IsFulfilled noMorebackColliderHit =
() => !this.MyPhysics.GetColliders<VehicleBackCollider>().Any();
// Define "back-collider-ended-touching" transition
 transitionNoMoreBackColliderTouched =
new FsmTransition(noMorebackColliderHit, MyFsmStates.DrivingForward) { Order = 1, Name = "no more touching others back-bumper-bar", };
// add Is-no-more-touching-back-collider transition stateDrivingOnOthersBackBumperBar.AddTransition(transitionNoMoreBackColliderTouched);

Ok, now it works in a different way than before. But it still cannot be better observed.

So the next thing I needed was a visual representation of what the finite state machine is “thinking”.

I wrote a Unity3D editor window to display this via a force-directed graph drawing:


See the complete FSM in action:

First (very simple) pedestrian pathfinding

The first approach for pedestrian pathfinding is now implemented. I chose an optimized version of the A* pathfinding with the jump point search algorithm. (For the vehicle implementation I used the Dijkstra algorithm, but this seems to be too greedy for the pedestrian pathfinding).

Collision detection and animation are still missing so the walk looks a little bit like a robot on roller-skates.

Creating class libraries for Unity3D using Visual Studio

The Visual Studio Tools are a great help when programming with C# for Unity3D.
But some things are still a little bit tricky, if the code base grows larger and you still want to create “clean code”.

Especially creating library assemblies to organize and/or reuse your code across multiple projects is not as easy as with normal Visual Studio projects. If you create a new class library project, you have to copy the DLL into the asset-folder of your Unity3D project.

You can´t create the project inside the Unity3D project path for two reasons:

  1. Unity will detect the *.CS files of your class library inside the Unity3D game project folder and will compile them (again) as part of the game project. (This is ok if you only want to share the *.CS files with other Unity projects. But in this case you should not create a class library project and just use clever namespaces instead to organize your code inside the C# files.)

  2. If you build the new library project inside Visual Studio, the Unity3D DLLs are copied into the asset-folder, too. This causes the build error “Assembly DLL name is reserved for internal use: […..]/UnityEngine.dll (did files generated by a build accidentally end up in your Assets/ folder?)”.

The first step to create the class library project:

Add a new class library project to your Visual Studio solution. Place the location outside of the Unity3D folder of your game project (especially outside the assets folder). 

In my case the new project is named “de.springwald.unity3d.toolbox” and my Unity3D project is called “MiniTrue”.

Now you should see something like this:

In most cases you will want to use Unity3D objects in your library.

The needed reference can be found at
c:\Program Files (x86)\Unity\Editor\Data\Managed\

After adding the references to your project it should look like this:

Now open the new project properties and change the framework to the same entry as your "UnityVs…CSharp" project.
In my case this is „Unity 3.5 .net Subset Base Class Libraries“.

For debugging purposes you should create the mono debug symbols by adding the following post-build command line:

"c:\Program Files (x86)\Unity\Editor\Data\Mono\lib\mono\2.0\pdb2mdb.exe" $(TargetPath)

Create a subfolder inside the Unity3D asset folder and call it like your new project.
For my project the name is “Assets\AdditionalDlls\de.springwald.unity3d.toolbox”.

The last problem to solve is making your new DLL useable in multiple Unity3D projects e.g. sharing them via GIT. Your asset folder path contains the name of your Unity3d project, so it´s not a good idea to place this information inside the library project.

But you can put it into a common parent folder of your Unity3D project and the new DLL project. Place a batch file called copyAdditionalDlls.bat into this parent folder and add it to the post-build event command line like this:


Place a simple copy command inside the a batch file to copy the library DLL files to the “Assets\AdditionalDlls\...” folder:

For my project folders structure this is the copy command:

Copy e:\MiniTrue\de.springwald.unity3d.toolbox\bin\de.springwald.unity3d.toolbox.* e:\MiniTrue\Unity3D\Assets\AdditionalDlls\de.springwald.unity3d.toolbox

That’s all. If you now build the new DLL inside Visual Studio it will be “beamed” into the asset folder of your Unity project and can be debugged, too.

Update 25.01.2015 - 23:20: pdb2mdb.exe has problems with methods containing "yield return"

While writing code for my class library suddenly the pdb2mdb.exe started to exit with “code -1”.

After searching for 2 hours I found this mono bug from 2011: “[Mono-bugs] [Bug 704702] New: pdb2mdb.exe fails on methods containing 'yield'”

Seems as if the pdb2mdb.exe delivered with Unity3D has this very old bug and it crashes when you use “yield” in your code.

Fortunately there is a newer version available, which you can include into your project using nuget.

To install the newer version of "Mono pdb2mdb", open the Package Manager Console (from the Tools menu, select Library

Package Manager and then click Package Manager Console) and run the following command:

PM> Install-Package Mono.pdb2mdb

The path to the pdb2mdb.exe also has to be changed inside the post build commands:

$(ProjectDir)packages\Mono.pdb2mdb.\tools\pdb2mdb.exe $(TargetPath)

First AI approach for the traffic system

With more than one vehicle on the road a little bit of artificial intelligence is needed. 

I decided to attach three Unity3D collider (with activated “trigger” property and one rigidbody component) to each vehicle:

  • An active front collider to detect if the vehicle is about to crash into another car or pedestrian
  • A passive body collider to be detected by the front collider of another vehicle
  • A passive back collider – also to be detected by another front collider


First idea of the collider and the AI behavior:

If the front collider of the vehicle hits a body collider it stops and tries to drive back a little bit. 

When the back collider is hit, the other car is probably just driving on the same track but with less speed. In this case the vehicle with the triggered front collider adjusts to the speed of the car in front of it.

The result looks more like a cartoon character using trial and error  than a defensive driving style. I call this AI behavior “Italian  driving mode” ;-)

A first animated video of some vehicles using the AI:


BTW: One thing I learned about Unity3Dwhile working on this: Because Unity seems to serialize enums as numbers and not by name: Use a flag number for every enum value. Otherwise when you change the order inside the enum definition the meaning swaps.