This describes how the position is solved in game world, and how is it converted to grid-like style.

This is sub-layout for documentation pages

Top

The game world is not grid-like style. That means, that there is infinite 2D plane, and system holds an array of objects along with their positions.
Therefore, this requires less memory than if an array of all squares in world would be held in memory.
This is done because of flexibility and reusability. I just have written the game engine like that.

In case of free movement, which would mean that player can move in any direction, to any point, there would be difficulties in implementation. Not saying that it can not be done, but the way how it can be done would be using lot of cpu and memory.
This addresses:

• Pathfinding, where system would have to find the closest path node to character, and then navigate. Considering that it would be common operation, this can be serious issue, considering a lot of players, monsters, game map portions, and game worlds.
• When using an ability, which would create projectile, which would damage any character on impact, this would make PVP impossible, as you might not be able to attack target player, if someone is between you and target, as he would collide with the projectile.

The grid-like style movement means, that whenewer you move your character, it will end up on one floortile (square). This is same as movement in Runescape.
It, however, does not mean, that the position of GameObjects could not be decimal, the position can be any number, but after movement is finally done, player will end up on one square.

2.1 Benefits of grid-like style

Now, the huge benefit is, that all that player sends to server as movement input, is target array indexes.
Unlike in the free-way-like movement, where any mouse change, mouse click and mouse rfelease had to be sent constantly to server to maintain movement.
This adds alot to server performance

The task is, being given any real \([X,Y]\) position in world, return appropriate indexes \([x, y]\) of virtual array.
As an illustration, let's have a look at one floor tile image:

3.1 The virtual array index

Let's consider, that each flootile has its size. If they are drawn correctly, they create isometric effect.
An \(x, y\) index can be assigned to each floorile, as displayed below:

Now, the indexes of such a virtual array are not stored anywhere. They are simply being computed dynamically.
Being given point \(A\) (as in image above), we want indexes \([0,0]\) to be returned. In case of point \(B\), we want indexes \([1,0]\) to be returned, and so on...

3.2.1 Theory

In order to solve this, let's imagine a bounding rectangle around all the floortiles. They are depicted in following image:

Then, choose such a rectangle such as it contains the point given inside (can be any rectangle that matches that criteria).
That rectangle is divided to 4 subrectangles (quadrants 1, 2, 3, 4). Each quadrant is divided in half as in the image:

The thing left to do is check in what quadrant is the point, and then in what part of subsquare it lies. Then, sufficient information is gathered to alter/return the final virtual array index.

3.2.2 Getting bounding rectangle

To ease things up, the first task will be to calculate the upper left corner of the bounding rectangle. Because there are many bounding rectangles (as in image above), it would get really complicated.
However, all rectangles that are overlapping others can be removed, leaving us only with following rectangles.

Now, this is sufficient for solution, as from all floortiles inside the rectangles, we can get to the adjacent ones using the calculation described above

3.2.3 Getting virtual arrayindex

When we have already the bounding box rectangle that contains the queried point, we want to know the virtual array index for the floortile which is fully contained in that rectangle.
For that purpose, all rectangles are given an index, as depicted in image here
For example, the bounding box around floortile with virtual array index \([1,1]\) has index \([1, 0]\)

From that index, the corresponding virtual array index is computed.
The reason why is this solved step by step is to modularize the problem and allow possibility to test all steps, making it easier to implement and develop.
Having the virtual array index candidate, we split the bounding rectangle to quadrants and determine where is the point. According to that, we eighter return the VAC, or we alter it accordingly.
Then, we have the result.

3.2.4 Calculation

• Let \(I=(x_i, y_i)\) be input values
• Let \(W, H\) be sizes of one floor tile texture
• Let \(P_v\) be virtual array index that belongs to bounding box that contains \(I\)
• Using integer division, calculate virtual array index that belongs to bounding rectangle in which is point. Applies:
  \(P_v = (\lfloor x_i / W \rfloor, \lfloor y_i / H \rfloor) \)
• Calculate \(r_c=(a, b)\) centre of bounding rectangle, and use it to determine in which quadrant is \(I\)
• Calculate appropriate line \(L\) and reference point \(P_r\) such as \(P_r\) lies outside the floortile.
• Calculate, whether \(I\) lies on the same side of \(L\) as \(P_r\), if so, alter virtual array index appropriately and return. Else, return \(P_v\)

One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray, starting from the point and going in any fixed direction, intersects the edges of the polygon. If the point is on the outside of the polygon the ray will intersect its edge an even number of times. If the point is on the inside of the polygon then it will intersect the edge an odd number of times. This method won't work if the point is on the edge of the polygon.

When player starts on map, he is always standing on a pathnode, and on some virtual square.
When client clicks on map on any point (let is be \(P_1\)), then on client side the position is modularized to figure out the virtual array index.
Then, the virtual array index is sent to server, and server moves player to such a position in the world (if possible)