A proposed solution for area spell cast bottleneck in TFS 1.3

spellCastConcept.cpp

#include <iostream>
#include <vector>
#include <math.h>
#include <cstdlib>
#include <algorithm>

using namespace std;

class Pos{
    public:
        int x;
        int y;

        Pos(int x, int y){
            this->x = x;
            this->y = y;
        };
};

class Matrix{
    private:
        int sizeX;
        int sizeY;
        vector<vector<int>> contents;

    public:
        Matrix(int sizeX, int sizeY){
            this->sizeX = sizeX;
            this->sizeY = sizeY;
            vector<int> column;
            for (int x = 0; x < sizeX; x++) {
                column.push_back(0);
            }

            vector<vector<int>> row;

            for (int y = 0; y < sizeY; y++){
                row.push_back(column);
            }

            this->contents = row;
        }

        Matrix(vector<vector<int>> matrixData) {
            this->sizeY = matrixData.size();
            this->sizeX = (sizeX = 0) ? 0 : matrixData[0].size();
            this->contents = matrixData;
        }

        Matrix clone(){
            Matrix m(this->contents);
            return m;
        }

        void setValue(int x, int y, int value){
            this->contents[y][x] = value;
        }

        void print(){
            for (int y = 0; y < sizeY; y++){
                for (int x = 0; x < sizeX; x++){
                    cout << contents[y][x];
                    if (x < sizeX-1)
                        cout << ", ";
                }

                cout << endl;
            }
        }

        Pos getSize(){
            return Pos(sizeX, sizeY);
        }

        int getValue(int x, int y){
            return contents[y][x];
        }

       Pos find(int value){
            for (int y = 0; y < sizeY; y++){
                for (int x = 0; x < sizeX; x++){
                    int v = contents[y][x];
                    if (v == value) {
                        return Pos(x, y);
                    }
                }
            }
        }
};

//get a line between two points
//based on Xiaolin Wu algorithm
vector<Pos> get2DLine(int x0, int y0, int x1, int y1)
{
	vector<Pos> line;
	if (x0 == x1 && y0 == y1) {
		return line;
	}

	//int endX = x1;
	//int endY = y1;
	//line.push_back({ x0, y0 });

	bool isSteep = abs(y1 - y0) > abs(x1 - x0);
	if (isSteep) {
		std::swap(x0, y0);
		std::swap(x1, y1);
	}

	bool flip = false;

	if (x0 > x1) {
        flip = true;
		std::swap(x0, x1);
		std::swap(y0, y1);
	}

	int dx = x1 - x0;
	int dy = y1 - y0;
	double grad = 1.0;

	if (dx != 0) {
		grad = dy * 1.0 / dx;
	}

	double interY = y0 + grad; //first y - intersection for the main loop

	if (isSteep) {
		for (int y = x0 + 1; y < x1; y++) {
			int newX = floor(interY);
			int newY = y;
			line.push_back(Pos(newX, newY));
			interY += grad;
		}
	} else {
		for (int x = x0 + 1; x < x1; x++) {
			int newX = x;
			int newY = floor(interY);
			line.push_back(Pos(newX, newY));
			interY += grad;
		}
	}

	//line.push_back({ endX, endY });
    if (flip){
        reverse(line.begin(), line.end());
    }

	return line;
}


Matrix getActualSpellArea(Matrix spell, Matrix obstacles){
    //get spell matrix size
    Pos mSize = spell.getSize();

    //create empty matrix to draw on
    Matrix canvas = obstacles.clone();

    //get player pos
    Pos playerPos = spell.find(3);

    for (int y = 0; y < mSize.y; y++){
        for (int x = 0; x < mSize.x; x++){
            int obstacleStatus = obstacles.getValue(x, y);
            int canvasStatus = canvas.getValue(x, y);

            if (canvasStatus == 0 && obstacleStatus == 0){
                vector<Pos> path = get2DLine(playerPos.x, playerPos.y, x, y);

                bool blocked = false;
                for (const auto& it : path) {
                    int pathX = it.x;
                    int pathY = it.y;

                    if (blocked) {
                        canvas.setValue(it.x, it.y, 1);
                    } else {
                        obstacleStatus = obstacles.getValue(it.x, it.y);
                        canvasStatus = canvas.getValue(it.x, it.y);

                        if (obstacleStatus == 1 || canvasStatus == 1){
                            blocked = true;
                            canvas.setValue(it.x, it.y, 1);
                        }
                    }
                }

                if(blocked){
                    canvas.setValue(x, y, 1);
                }
            } else {
                if (x != playerPos.x && y != playerPos.y){
                    canvas.setValue(x, y, 1);
                }
            }

            int spellStatus = spell.getValue(x, y);
            int obstacle = obstacles.getValue(x, y);


        }
    }

    return canvas;
}

int main(){

    //set up spell matrix
    vector<vector<int>> s(
        {
            {1, 1, 1, 1, 1},
            {0, 1, 1, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 3, 0, 0}
        }
    );
    Matrix spell = Matrix(s);

    //print matrix
    spell.print();
    cout << endl;

    //get player pos
    Pos playerPos = spell.find(3);
    cout << "player pos: " << playerPos.x << ", " << playerPos.y << endl;

    //get matrix size
    Pos mSize = spell.getSize();
    cout << "matrix size: " << mSize.x << ", " << mSize.y << endl;

    //get value from player pos
    int value = spell.getValue(playerPos.x, playerPos.y);
    cout << "value read from player pos: " << value << endl;
    cout << endl;

    //set up obstacle matrix
    //Current tfs implementation calls isSightClear which checks attributes of same tile a few times.
    //This implementation would scan area only once and do everything else on a small matrix.
    vector<vector<int>> o(
        {
            {0, 0, 0, 0, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0}
        }
    );
    Matrix obstacles = Matrix(o);

    cout << "obstacles found: " << endl;
    obstacles.print();
    cout << endl;

    //use two matrices and sight line to generate the final result
    Matrix result = getActualSpellArea(spell, obstacles);

    cout << "final area:" << endl;
    result.print();

    return 0;
}