To be able to code such kind of game, the main part is to code those "people" which do the actions and use your service. Each person is a separated entity and have his/her own goal(s). You don't control directly the people but you can hire staff to do certain types of jobs.
So how to start such game kind? Well my first steps have been to create a 2D map (nothing new here), and have some "actors" with all their AI. Currently the AI just tell them to reach a given point or at least to go as nearby as possible.
After some trials, I clearly see that my code slows down way too much for the number of people I want to run and therefore I was wondering if my JS code would be so much slower than a C# code (which is nearly the speed of a compiled C++ code under Windows).
So let's start with a full use case in JS:
https://jsfiddle.net/a_bertrand/zcp1ygwy/
If you run it, wait a bit to get the result. It takes me around 4-5 secs.
Now for the C# counter part:
Code: Select all
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
public class Program
{
public static void Main(string[] args)
{
var game = new Game();
var w = new Stopwatch();
w.Start();
for (var i = 0; i < 100; i++)
game.HandleLogic();
w.Stop();
Console.WriteLine(w.Elapsed.TotalMilliseconds);
}
class Game
{
public int nbPathAvailable;
public int gameSpeed = 4;
public int[, ] map;
public int[, ] objectLayer;
public List<Actor> actors = new List<Actor>();
private Random rnd = new Random();
public Game()
{
var mapSize = 100;
// Fill with grass
this.map = new int[mapSize, mapSize];
this.objectLayer = new int[mapSize, mapSize];
for (var i = 0; i < mapSize; i++)
{
for (var j = 0; j < mapSize; j++)
{
this.map[i, j] = 2;
this.objectLayer[i, j] = 0;
}
}
// Make the road
for (var i = 0; i < mapSize; i++)
{
this.map[2, i] = 0;
this.map[3, i] = 1;
}
// Make the building
for (var x = 0; x < 30; x++)
for (var y = 0; y < 20; y++)
this.map[x + 6, y + 10] = 3;
// Make the walls, beside a entry point
for (var x = 0; x < 30; x++)
{
for (var y = 0; y < 20; y++)
{
if ((x == 0 || x == 29 || y == 0 || y == 19) && !(x == 0 && y > 8 && y < 13))
this.objectLayer[x + 6, y + 10] = 4;
}
}
for (var i = 0; i < 300; i++)
{
var actor = new Actor(this);
for (var j = 0; j < 10; j++)
{
actor.X = (int)Math.Round(rnd.NextDouble() * (mapSize - 2) * 32 + 16);
actor.Y = (int)Math.Round(rnd.NextDouble() * (mapSize - 2) * 32 + 16);
actor.GoalX = 500;
actor.GoalY = 800;
if (!actor.Collide(actor.X, actor.Y))
{
this.actors.Add(actor);
break;
}
}
}
}
public void HandleLogic()
{
this.nbPathAvailable = 2;
this.actors.Sort((a, b) =>
{
return b.lastPath - a.lastPath;
}
);
for (var gs = 0; gs < this.gameSpeed; gs++)
{
var actorArray = this.actors.ToArray();
for (var i = 0; i < actorArray.Length; i++)
actorArray[i].Handle();
}
}
}
class PathStep : PathPoint
{
public int steps;
public List<PathStep> path;
public int cost;
public double distance;
public int operations;
}
class PathPoint
{
public int x;
public int y;
}
class PathSolver
{
//private visitedStep: PathStep[] = [];
Dictionary<string, bool> visitedStep = new Dictionary<string, bool>();
List<PathStep> todoStep;
int goalX;
int goalY;
int operations;
Actor actor;
int maxDistance;
int stepSize;
public static Queue<PathPoint> Solve(int startX, int startY, int goalX, int goalY, int maxDistance, int stepSize, Actor actor)
{
var solver = new PathSolver(startX, startY, goalX, goalY, maxDistance, stepSize, actor);
var path = solver.solve();
if (path == null)
return null;
var result = new Queue<PathPoint>();
for (var i = 0; i < path.path.Count; i++)
{
result.Enqueue(new PathPoint{x = path.path[i].x, y = path.path[i].y});
}
// Add the goal too
if (result.Count > 0)
result.Enqueue(new PathPoint{x = goalX, y = goalY});
return result;
}
private PathStep solve()
{
while (this.todoStep.Count > 0 && this.operations < 2000)
{
this.operations++;
var res = this.calcStep();
if (res != null)
return res;
}
return null;
}
public PathSolver(int startX, int startY, int goalX, int goalY, int maxDistance, int stepSize, Actor actor)
{
this.visitedStep = new Dictionary<string, bool>();
this.todoStep = new List<PathStep>();
this.goalX = goalX;
this.goalY = goalY;
this.operations = 0;
this.actor = actor;
this.maxDistance = maxDistance;
this.stepSize = stepSize;
var a = startX - this.goalX;
var b = startY - this.goalY;
this.todoStep.Add(new PathStep{x = startX, y = startY, steps = 0, path = new List<PathStep>(), operations = 0, distance = Math.Sqrt(a * a + b * b), cost = 0});
this.visit(this.todoStep[0]);
}
private bool isVisited(PathStep coord)
{
var s = "" + coord.x + "," + coord.y;
return this.visitedStep.ContainsKey(s);
}
private void visit(PathStep coord)
{
var s = "" + coord.x + "," + coord.y;
this.visitedStep.Add("" + coord.x + "," + coord.y, true);
}
private PathStep addCoordinate(PathStep coord, int x, int y, int cost)
{
x = coord.x + x;
y = coord.y + y;
var path = coord.path.ToList();
path.Add(coord);
var a = x - this.goalX;
var b = y - this.goalY;
var res = new PathStep{x = x, y = y, steps = coord.steps + cost, path = path, distance = Math.Sqrt(a * a + b * b), operations = this.operations, cost = 0};
res.cost = (int)(res.steps + res.distance * 2);
return res;
}
private PathStep calcStep()
{
if (this.operations % 5 == 0)
this.todoStep.Sort((a, b) => a.cost - b.cost);
var s = this.todoStep[0];
this.todoStep.RemoveAt(0);
//if (Math.abs(s.x-this.goalX) <= this.speed && Math.abs(s.y-this.goalY) <= this.speed)
//if (s.distance < this.speed)
if (s.distance <= this.stepSize * 2)
{
s.operations = this.operations;
return s;
}
if (this.todoStep.Count > 500000)
{
this.todoStep.Clear();
return null;
}
if (s.steps > 50000)
return null;
var newCoords = new PathStep[]{this.addCoordinate(s, -1 * this.stepSize, 0, 1), this.addCoordinate(s, 0, -1 * this.stepSize, 1), this.addCoordinate(s, 1 * this.stepSize, 0, 1), this.addCoordinate(s, 0, 1 * this.stepSize, 1), this.addCoordinate(s, -1 * this.stepSize, -1 * this.stepSize, 2), this.addCoordinate(s, -1 * this.stepSize, 1 * this.stepSize, 2), this.addCoordinate(s, 1 * this.stepSize, -1 * this.stepSize, 2), this.addCoordinate(s, 1 * this.stepSize, 1 * this.stepSize, 2)};
for (var i = 0; i < newCoords.Length; i++)
{
var c = newCoords[i];
if (c == null)
continue;
if (!this.isVisited(c) && c.distance < this.maxDistance)
{
this.visit(c);
if (!this.actor.Collide(c.x, c.y))
this.todoStep.Add(c);
}
}
return null;
}
}
class Actor
{
public int X = 0;
public int Y = 0;
public int GoalX = 0;
public int GoalY = 0;
public double Direction = 0;
public int Speed = 2;
public int CollisionSize = 16;
private Queue<PathPoint> path = null;
public int lastPath = 1000;
private bool reached = false;
private int waitTimer = 0;
private Game game;
public Actor(Game game)
{
this.game = game;
}
public void Handle()
{
if (this.reached)
{
/*this.waitTimer--;
if (this.waitTimer < 0)
{
this.reached = false;
this.GoalX = 100;
this.GoalY = 100;
this.path = null;
}*/
return;
}
var a = this.GoalX - this.X;
var b = this.GoalY - this.Y;
var d = Math.Sqrt(a * a + b * b);
if (this.path == null && d > 16)
{
if (game.nbPathAvailable > 0)
{
game.nbPathAvailable--;
this.lastPath = 0;
var step = this.Speed * 8;
if (d < 128)
step = this.Speed;
var gx = this.GoalX;
var gy = this.GoalY;
for (var i = 0; i < 60000 && this.Collide(gx, gy); i++)
{
gx = (int)(this.GoalX + Math.Cos(i / 20.0) * i / 100.0);
gy = (int)(this.GoalY + Math.Sin(i / 20.0) * i / 100.0);
}
if (!this.Collide(gx, gy))
{
this.path = PathSolver.Solve(this.X, this.Y, gx, gy, 30000, step, this);
}
}
else
{
this.lastPath++;
return;
}
}
if (this.path != null && this.path.Count == 0)
{
this.waitTimer = 1000;
this.reached = true;
}
else if (this.path != null && this.path.Count > 0)
{
var x = this.path.Peek().x;
var y = this.path.Peek().y;
if (this.Collide(x, y))
this.path = null;
else
{
a = x - this.X;
b = y - this.Y;
d = Math.Sqrt(a * a + b * b);
if (d <= this.Speed)
{
this.X = x;
this.Y = y;
this.path.Dequeue();
}
else
{
this.Direction = Actor.CalculateAngle(a, b);
var vx = Math.Cos(this.Direction) * this.Speed;
var vy = Math.Sin(this.Direction) * this.Speed;
x = (int)Math.Round(this.X + vx);
y = (int)Math.Round(this.Y + vy);
if (!this.Collide(x, y))
{
this.X = x;
this.Y = y;
}
else if (!this.Collide(x + 1, y))
{
this.X = x + 1;
this.Y = y;
}
else if (!this.Collide(x - 1, y))
{
this.X = x - 1;
this.Y = y;
}
else if (!this.Collide(x, y + 1))
{
this.X = x;
this.Y = y + 1;
}
else if (!this.Collide(x, y - 1))
{
this.X = x;
this.Y = y - 1;
}
else
this.path = null;
}
}
}
}
public bool Collide(int x, int y)
{
// Check if it collides with an object
for (var a = -1; a < 2; a++)
{
for (var b = -1; b < 2; b++)
{
var tx = (int)Math.Floor((x - this.CollisionSize / 2.0 * a) / 32);
var ty = (int)Math.Floor((y - this.CollisionSize / 2.0 * b) / 32);
if (tx < 0 || ty < 0 || tx >= 100 || ty >= 100)
return true;
if (game.objectLayer[tx, ty] != 0)
return true;
}
}
for (var i = 0; i < game.actors.Count; i++)
{
if (game.actors[i] == this)
continue;
var a = game.actors[i].X - x;
var b = game.actors[i].Y - y;
var d = Math.Sqrt(a * a + b * b);
if (d < Math.Max(this.CollisionSize, game.actors[i].CollisionSize))
return true;
}
return false;
}
public void SetGoal(int x, int y)
{
this.path = null;
this.GoalX = x;
this.GoalY = y;
this.reached = false;
}
public void Kill()
{
game.actors.Remove(this);
}
public static double CalculateAngle(double ad, double op)
{
var angle = 0.0;
if (ad == 0.0) // Avoid angles of 0 where it would make a division by 0
ad = 0.00001;
// Get the angle formed by the line
angle = Math.Atan(op / ad);
if (ad < 0.0)
{
angle = Math.PI * 2.0 - angle;
angle = Math.PI - angle;
}
while (angle < 0)
angle += Math.PI * 2.0;
return angle;
}
}
}
So what did I learn from this test? Basically JS has nothing to be shy of in terms of performances, as long as you run inside Chrome, and it's not a rendering issue (which then can be slower than DX or Open GL).
Remains that my code is not performant enough, and it's not a question of technology / language but what I do with it.
If you wonder why my code is too slow, well it's the collision detection between people which slows things down, so I need to either optimize the collision detection or avoid collision detection with other people inside the path solving (which may be the right choice).