Unity's / C# limitations with high number of object instances?
Hi everyone! I've been working lately on "porting" Hopson's game "Empires" (you can check it out here, and see a brief description below) from C++ to C#, in Unity. My main concern was that C# is considered to be slower compared to C++, and since the game involves a huge amount of object instances (again, details below), this might make the game impossible to play.
Some words on the concept of the game:
The "board" of the game is a map, devided to 2 colors: green for land, and blue for sea.
"People" are placed on land tiles on the map. Each person belongs to a "tribe", which might be considered to different players. Additionaly, each person has "age", "strengh" and "reproduction time".
Every tick of the game ("turn" if you will), each person will get his age added by one. once the age corsses the strengh value, this person dies. If the person doesn't die, he get his reproduction timer value added by one, and it is checked against a constant reproduction value. if the later is smaller, a new "person" is born in a random location around the "parent" and the reproduction timer is zeroed.
There are some other uses and implications to the strengh value and some other I didn't even mention, as the problems show up even by just implimanting the system described above.
When the game starts, several persons of each tribe are placed in random locations over the map, and the game starts ticking.
An important detail: the persons are NOT game objects, but are "just" objects.
And now to the problem: When the game starts, and for the first few moments, it runs smoothly. By setting the reproduction rate at around half the stregh value, I allowed the persons to reproduce faster than dying, and respectivly, more and more persons are needed to be checked every tick of the game. At around 13,000 persons, the FPS drops so low (less than 10), that the game is not playable anymore. This is in contrast to the original "Empires" game, which handles hundreds of thousands of persons without bothering the CPU.
All of this leads to the question: is it possible that "porting" this kind of codes, that requires handling this many of object instances, is just not possible in C#? Or is it possible that working in Unity has its toll when working on this kind of jobs? Of course, in case my optimization job is to blame, I'd be more than greatful for every tip on that.
last but not least, my way of implamenting "Empires" in C#:
BoardLocation.cs: Simple calss to simplify referring to locations on the board (basicly a Vector2 of ints):
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class BoardLocation
{
public int x;
public int y;
public BoardLocation() {}
public BoardLocation(int _x, int _y)
{
x = _x;
y = _y;
}
/// <summary>
/// Get a random location on board.
/// Optionaly add a restriction to avoid being too close to board edges
/// </summary>
/// <param name="board">The board where the random location is required</param>
/// <param name="restrict_x">Restrict a distance from board edge (x vector)</param>
/// <param name="restrict_y">Restrict a distance from board edge (y vector)</param>
/// <returns></returns>
public static BoardLocation GetRandomLocation(Person [,] board, int restrict_x = 0, int restrict_y = 0)
{
BoardLocation randLoc = new BoardLocation();
randLoc.x = Random.Range(restrict_x / 2, board.GetLength(0) - restrict_x / 2);
randLoc.y = Random.Range(restrict_y / 2, board.GetLength(1) - restrict_y / 2);
return randLoc;
}
}
World.cs: Holds and "board" and acts as a gamecontroller:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class World : MonoBehaviour
{
public static World current; // singleton field
public float gameSpeed; // Used to determine the rate of game ticks
private Sprite worldMapTexture; // A reference to the sprite used as world map
public Person[,] board; // The actual board
public int startingAreaSize; // Determines the area * area around random starting zones
//where persons will be spawned
public int startingPersons; // The amount of persons to spawn of every tribe
//at the beggining of the game
public Color seaColor; // Color of sea pixels. Basicly blue
// Colors of tribes. Tribe 0 is always an empty place on the board.
// TODO add a tribe class with more data (name, icon etc...)
public Color[] tribes;
// A list for persons that were spawned. Every game tick, this list will be itterated and the persons will
// be "told" to proccess a turn (age, reproduce, die etc)
public List<Person> activePersons = new List<Person>();
// A queue holding the persons that were born this turn.
// Every turn, it will be emptied into the "active persons" list.
public Queue<Person> personsToAdd = new Queue<Person>();
// A queue holding the persons who died this turn.
// Every turn, it will be emptied, and the persons who died will be removes from "active persons" list.
public Queue<Person> personsToRemove = new Queue<Person>();
private int turn = 0; // Turns counter
// Active persons counter
// TODO: add a counter for every different tribe
public Text personsCounter;
public Text turnsCounter; // A reference to the GUI for the turns counter
private void Awake()
{
// Assign singleton
current = this;
// Get refernece for the sprite, which is used as the map
worldMapTexture = GetComponent<SpriteRenderer>().sprite;
}
void Start ()
{
// Configure the board size
int map_x = Mathf.FloorToInt(worldMapTexture.rect.width);
int map_y = Mathf.FloorToInt(worldMapTexture.rect.height);
board = new Person[map_x, map_y];
// pawn first persons
SpawnStartingPersons(tribes.Length);
// start off the game!
InvokeRepeating("GameTick", 0, gameSpeed);
}
/// <summary>
/// Spawn the starting persons for every tribe. Called at the beginning of a game.
/// </summary>
/// <param name="numberOfTribes">Amount of tribes to start persons for.</param>
private void SpawnStartingPersons(int numberOfTribes)
{
for (int i = 1; i < numberOfTribes; i++)
{
int personsToPlace = startingPersons;
BoardLocation randomLocation = new BoardLocation();
do
{
randomLocation = BoardLocation.GetRandomLocation(board,startingAreaSize,startingAreaSize);
} while (IsPixelSea(randomLocation.x, randomLocation.y) == true);
do
{
for (int y = randomLocation.y - startingAreaSize / 2; y < randomLocation.y + startingAreaSize / 2; y++)
{
for (int x = randomLocation.x - startingAreaSize / 2; x < randomLocation.x + startingAreaSize / 2; x++)
{
BoardLocation bloc = new BoardLocation(x, y);
int isPlacing = Random.Range(0, 2);
if (isPlacing == 0)
{
continue;
}
bool didPlace = PlacePerson(i, bloc);
if (didPlace == false)
{
continue;
}
if (personsToPlace-- <= 0)
{
break;
}
}
if (personsToPlace <= 0)
{
break;
}
}
} while (personsToPlace > 0);
}
}
/// <summary>
/// Place a single person at a designated location on board.
/// Returns true if the person was placed succesfuly, and false in case of failure.
/// </summary>
/// <param name="tribe">The tribe which the new person will belong to.</param>
/// <param name="boardLocation">The location on board where the person will appear at.</param>
/// <returns></returns>
private bool PlacePerson(int tribe, BoardLocation boardLocation)
{
if (IsPixelSea(boardLocation.x, boardLocation.y) == true)
{
// This is a sea pixel, a person can;t be placed here!
return false;
}
// Create a new person instance and send it his tribe, location and if he is ill
board[boardLocation.x, boardLocation.y] = new Person(tribe, boardLocation, false);
// Paint the person on map
worldMapTexture.texture.SetPixel(boardLocation.x, boardLocation.y, tribes[tribe]);
// Add the new person to a queue, which will allow it to be
// proccessed on the next turn
personsToAdd.Enqueue(board[boardLocation.x, boardLocation.y]);
return true;
}
/// <summary>
/// Kills the person and removes him from the game.
/// </summary>
/// <param name="p">The person to kill.</param>
public void KillPerson(Person p)
{
// Change the tribe index of the person to 0,
//so a different person will be able to spawn here some day.
board[p.boardLocation.x, p.boardLocation.y] = new Person(0, p.boardLocation, false);
// Change the color of the place this person used to occupy to empty
worldMapTexture.texture.SetPixel(p.boardLocation.x, p.boardLocation.y, tribes[0]);
// Add the dead person to a queue, which will allow it to be
// removed from the active persons list in the end of the turn
personsToRemove.Enqueue(p);
}
/// <summary>
/// Main method for the game. Handles telling every active person to proccess his turn; Updates GUIs;
/// and handles repainting the world map. Called at the beginning of the game.
/// </summary>
private void GameTick()
{
// Add 1 to the turn counter and update the GUI
turn++;
turnsCounter.text = "Turn: " + turn.ToString();
// Update the GUI for active persons counter
personsCounter.text = "Active persons = " + activePersons.Count;
// Itterate through every active person and tell him to proccess his turn
foreach(Person p in activePersons)
{
p.PlayTick();
}
// Pop the queue which holds the persons who were born, and add them to
// the active persons list
//Debug.Log("people to remove: " + personsToRemove.Count);
while (personsToRemove.Count > 0)
{
activePersons.Remove(personsToRemove.Dequeue());
}
// Pop the queue which holds the persons who died, and remove them from
// the active persons list
//Debug.Log("people to add: " + personsToAdd.Count);
while (personsToAdd.Count > 0)
{
activePersons.Add(personsToAdd.Dequeue());
}
// Repaint the world map
worldMapTexture.texture.Apply();
}
/// <summary>
/// Returns true if a location is in sea, and false if it's land.
/// </summary>
/// <param name="loc_x">The x vector of the checked location</param>
/// <param name="loc_y">The y vector of the checked location</param>
/// <returns></returns>
private bool IsPixelSea(int loc_x, int loc_y)
{
// TODO add a system to filter unavailable locations (x or y smaller than 0 etc)
if (worldMapTexture.texture.GetPixel(loc_x, loc_y) == seaColor)
{
return true;
}
return false;
}
/// <summary>
/// Returns true if a location is unoccupied by some person, and false if it is occupied.
/// </summary>
/// <param name="loc_x">The x vector of the checked location</param>
/// <param name="loc_y">The y vector of the checked location</param>
/// <returns></returns>
private bool IsPixelEmptyLand(int loc_x, int loc_y)
{
if (board[loc_x, loc_y] == null)
{
return true;
}
if (board[loc_x, loc_y].tribeID == 0)
{
return true;
}
return false;
}
/// <summary>
/// Creates a new person, in case the location is valid.
/// The new person will inherent some properties from his parent.
/// Returns true if the person was created successfuly, and false in case of failure.
/// </summary>
/// <param name="parent">The parent which will give properties to the new person.</param>
/// <param name="bloc">The location where the new person is supposed to be placed.</param>
/// <returns></returns>
public bool Reproduce(Person parent, BoardLocation bloc)
{
// If the board location is at sea, do nothing
if (IsPixelSea(bloc.x, bloc.y) == true)
{
return false;
}
// If the board location is empty, reproduce!
if (IsPixelEmptyLand(bloc.x, bloc.y) == true)
{
// TODO add inherenting system
PlacePerson(parent.tribeID, bloc);
return true;
}
// If the board location is occupied by a person from a different tribe, challenge it
// TODO add challenge system
return false;
}
/// <summary>
/// Test if a new person will be born to an already occupied location.
/// </summary>
/// <param name="challenger">The new born person</param>
/// <param name="defender">The already present person</param>
/// <returns></returns>
private bool ChallengeLocation (Person challenger, Person defender)
{
// TODO actually implament system
if (challenger.strengh <= defender.strengh)
{
return false;
}
return true;
}
}
Person.cs: The class for persons:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Person
{
public int tribeID;
public BoardLocation boardLocation;
public float strengh = 10;
public int age = 0;
public bool ill;
public float reproductionTimer;
private float reproductionRate = 1;
private BoardLocation[] neighbors; // The 4 locations sorrounding this person.
// Used when randomizing a place for a new born person.
/// <summary>
/// Constuctor for person.
/// </summary>
/// <param name="_tribeID">The trive this person will belong to.</param>
/// <param name="_boardLocation">The location where this person will be placed at.</param>
/// <param name="_ill">Is this person ill?</param>
public Person (int _tribeID, BoardLocation _boardLocation, bool _ill)
{
tribeID = _tribeID;
boardLocation = _boardLocation;
reproductionRate += Random.Range(0, 5);
strengh += Random.Range(-5, 5);
ill = _ill;
// Neighbors are collected on spawn, to reduce calls every turn
neighbors = GetNeighbors();
}
/// <summary>
/// Get the 4 neighbors of a person (East, South, West, North).
/// </summary>
/// <returns></returns>
public BoardLocation[] GetNeighbors()
{
BoardLocation[] ns = new BoardLocation[4];
// E, S, W, N
ns[0] = new BoardLocation(boardLocation.x + 1, boardLocation.y);
ns[1] = new BoardLocation(boardLocation.x, boardLocation.y - 1);
ns[2] = new BoardLocation(boardLocation.x - 1, boardLocation.y);
ns[3] = new BoardLocation(boardLocation.x, boardLocation.y + 1);
return ns;
}
/// <summary>
/// Main method for a person. Proccess age, reproduction etc.
/// </summary>
public void PlayTick()
{
// Add 1 to age and check if person should die of old age
if (age++ > strengh)
{
Die();
return;
}
// Add 1 to reproduction timer, and if passed reproduction rate, bore a new person
if (reproductionTimer++ > reproductionRate)
{
Reproduce();
}
}
/// <summary>
/// Bore a new person from this one, at a randomized neighbored location.
/// </summary>
private void Reproduce()
{
reproductionTimer = 0;
int randomPixel = Random.Range(0, neighbors.Length);
World.current.Reproduce(this, neighbors[randomPixel]);
}
/// <summary>
/// Kill the person.
/// </summary>
public void Die()
{
World.current.KillPerson(this);
}
}
If you got up to here, than I already owe you thanks! :D But I'll be even more greatful for any reply.
Thanks alot in advance!
Answer by Bunny83 · Sep 03, 2017 at 01:22 PM
I would love to write a more detailed answer since there's a lot room for improvement. However I'm currently not home (until we) and I'm just writing on my tablet.
I'll give you some points you want to change \ improve:
First of all you have an allocation nightmare. You allocate too many classes \ arrays when it's not necessary.
for example your BoardLocation class really should be a struct and not a class.
also your get neighbors method should not return an array. Either change the method so you can pass in a list or array which is filled by the method. This way you can reuse the list \ array. Or since at most you can have 4 neighbors you may just use a struct as well.
List.Remove is quite taxing especially when you have many objects in the list. It would be better to remember the dead state inside the person itself and just use a book to mark the list dirty and remove all dead objects in one go though the list. By remove I don't mean using the Remove method but just fill the gaps manually. List remove has to move all following elements one to the front.
There might be other thing you can improve, but it's actually hard to read the word wrapped code with the interleaved long comments on my tablet.
When I'm back home in a few days I might add some more suggestions and explanations.
edit
I'm back home and finally have a proper keyboard to write -.-
As i mentioned above you want to replace your "BoardLocation class" by a struct. I've written a Vector3 equivalent with integer values called Vector3i. You can do the same for a 2d variant if you fear the additional coordinate.
The difference between classes and structs is much greater in C# than it is in C++. In C++ a class and a struct is actually the exact same thing, the only difference there is that the default visibility inside a class is private and in a struct it's public.
In C# however there's a huge difference. A class is always a reference type which is always allocated on the heap. There's no way to have a "local class instance". Structs on the other hand are value types (like the primitive datatypes, byte, int, float, ...). Local valuetype variables are stored on the stack, so they do not require a memory allocation on the heap. If you have a class that has a value type field, the memory for the value type is part of the class instance.
There is no real limit how many class instances you can have besides the available memory. I've once made a Mandelbrot generator that does not use the usual approach and calculating pixel by pixel but instead does one iteration on all pixels at the same time. Even the webGL build (resolution of 960x600 about 0.5M pixels) runs quite smooth (even it's a webGL build).
It's important to avoid memory allocations for two reasons:
memory allocations are slow
unreferenced allocated memory need to be garbage collected which can be even slower and is unpredictable.
To handle your neighbors you could simply use a struct that holds
public struct BoardNeighbors
{
public Vector2i pos;
public Vector2i up { get { return new Vector2i(pos.x, pos.y + 1);}}
public Vector2i down { get { return new Vector2i(pos.x, pos.y - 1);}}
public Vector2i right { get { return new Vector2i(pos.x + 1, pos.y);}}
public Vector2i left { get { return new Vector2i(pos.x - 1, pos.y);}}
public BoardNeighbors(Vector2i aPos)
{
pos = aPos;
}
public Vector2i this[int aIndex]
{
switch(aIndex)
{
case 0: return right;
case 1: return down;
case 2: return left;
case 3: return up;
}
throw new System.IndexOutOfRangeException("aIndex is out of range");
}
}
This struct only requires a single "Vector2i" and calculates the neighbor positions on the fly. Alternatively you can use one of the "StructLists" i've created. They basically can be used like normal generic Lists but they have a fix capacity of either 4 or 8 elements. Since they are structs they don't require any memory allocation on the heap. They are quite handy if you want to return a collection from a method that only contains a small number of elements. In your case it might be "0 - 4" elements.
Next thing you could do is to use some sort of object pool if you have objects which frequently "die" or are recreated / replaced.
Like Glurth said you may want to replace your "active" list either by a HashSet or turn your Person class into a "linked list node". That way adding / removing elements to / from the list is basically for free. A List quickly becomes very inefficient when you need to add / remove elements randomly.
Another way is to use two queues or List and time you process the list you copy all elements you want to keep into the second list. At the end you just clear the current list (but keep the capacity) and just swap the list. This approach is quite common for cases where you will need to iterate through all elements each frame anyways.
I would also recommend to decouple the simulation from the visual update. This could be done with a custom fixed update (also a helper i've wrote some time ago -.-).
Hi @Bunny83, thanks alot for your answer! I'll start working on the things you wrote. I'd appreciate if you could put more of your experience into this case, as this is probably my weakest point: I can make things work great, but they won't always be pretty, and it seems that in this project, "pretty" is a must-have...
Thanks alot again for your time!
Since you use such large number of objects, and it looks like you don't need to serialize them, nor need them iterated in any particular order, so a List may not be the best data-structure for the activePersons
member. $$anonymous$$ight want to check out HashSet < T >
https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx https://stackoverflow.com/questions/150750/hashset-vs-list-performance
Thanks alot @Glurth , changing the data structure from list to HashSet did miracles to game speed. As for now, the map can fill totally, and the game works just fine! That's over 200k objects tunning at the same time! Just to make sure I got it right, HashSets not being iterated in a particular order means every time I iterate them using Foreach, the order is random? or there is still some sort of order?
Thanks again!
Well, it's in SO$$anonymous$$E kind of order, it is a computer program after all ;)
That said; "No particular order" means YOUR code should not expect it to be random, nor expect it to NOT be random.