This is sub-layout for documentation pages

Top

Sprite depth means, that character will be displayed before / behind a wall sprite, depending on the character's position.
This is achieved by grouping such objects, that would participate in the depth sorting, into a container. Then, every tingle time, when any object changes it's vai position, the container is sorted using quicksort to achieve the depth draw ing functionality.

We will define PC player as a human, who is sitting behind the computer, which is running the client side code of our game, where the client side code is our field of study.
Current map is a map, in which is the PC player

A depth reference point is a point that every object, which is participating in the sprite depth sorting, has. On the gif image is displayed as a blue dot. All obvjects are then sorted using only this point.

We will define a container of items, that we want to sort. The container for these items will be a two-way linked Linked list
We will be maintaining this container in sorted order, sorting it in real time. That way, we achieve correct sprite depth for the game in all situations.
Obviously, optimalization and speed is the main concern here, and in following lines will be explained, how the maximum optimalization was achieved.

We further maintain a hashmap, where key is object id, and value is pointer to the relevant LinkedList node

3.1 Building the container

The container will be created, and all the new content will be added to the empty container only and only if the PC player will transition to a new map / connect to game / map.
All the items in the sort layer are added to the container, running at O(n) complexity Then, the container is sorted using mergesort algorithm, running in O(n * log n) complexity.
Entire action will be running in O(n * log n + n) = O(n * log n) time

3.2 Adding an antity to the container

Considering, that the adding action is not a part of building a container, then a new element will be added to the container, iif any non-PC player will connect to current map or any NPC will appear in the current map, or monster dies (and therefore, it needs to be reinserted on client side only to free the ID)
Adding such an item to a linked list is using insert sort, running at O(n) complexity

Note: as we have a linked list, please, keep in mind, that using a binary search for inserting the element would run at O(n) complexity aswell, but there would be more allocations and operations, making the solution less performant!

3.3 Changing an antity inside the container

An existing element A in the container would be changed, iif element A changes it's VAI position.
If an alement A in the container is changed supposed to be changed, then following will happen:

• Remove element A from the container (O(1), we use hashmap of pointers to LinkedList nodes)
• Use insert sort to insert the element A to the container (O(n))

If the element A would be changed, and then the entire container sorted again, we would end up with O(n * log n) complexity. So using solution stated above, we save n operations in the worst case.

3.4 Deleting an antity from the container

An existing element A in the container would be deleted, iif element A dissapears from the map.
That can be caused by (but is not limited only to) following events:

• Player disconnects
• Monster is killed
• Monster / Player is killed, and must be reinserted to free an ID

If the element A would be deleted, we use lookup hashmap and delete the element from containers, ending up with O(1) complexity.

It is worth mentioning, that even when the container was sorted at any of the events above, and quicksort algorithm was used (O(n * n)), the application ran flawlessly, without any issue and laggs.
Therefore, the optimalization stated above is not bringing any serious improvement to the project at all, but it is offering asymptotically faster running speed, so why shall it not be used...?