Topics

1

General / Slow performance with A*

« on: June 25, 2015, 01:29:58 pm »

Hi everyone,
I am having a problem with slowdown in a project of mine. I am trying to get a basic AStar implementation going, finding a path from a tile to another. At this point I have it working if I create the path outside of the 'while(window.isOpen())' loop, but if I put it inside, even under a keypress conditional, I get a lot of slowdown.
This makes me think there is some issue with something being done too many times, but I've gone over all the relevant code and a ton of websites and I can't find anything. Even stranger, when I uncomment the code in the keypress conditional, it does nothing, then on the second press finds a path to the cursor, then on any other presses does nothing again. All pretty slowly, of course.

Hoping you guys can help point me in the right direction.
Here is the main code, pared down as much as I can:

extern const int TILESIZE = 32;
extern const int MAPSIZE = 11;

#include <SFML/Graphics.hpp>
#include "Tile.h"
#include "Layer.h"
#include "CollisionLayer.h"
#include "Cursor.h"
#include "EventHandler.h"
#include "Unit.h"
#include "Units.h"
#include "Path.h"
int main()
{
        sf::RenderWindow window(sf::VideoMode(640, 480), "Joyous Day!");
        Layer testLayer(MAPSIZE, MAPSIZE);
        Cursor testCursor;
        Path testPath(testLayer.getTileVector()[9][9], testLayer.getTileVector()[1][2]); //This is the creation of the path object, it takes in an origin and a destination tile.      
        std::vector<Tile> path = testPath.findPath(testLayer); //The findPath function does most of the work. It works for the example tiles

        bool rightPressed = false;

        while (window.isOpen())
        {      
                window.clear();
                sf::Event event;
                while (window.pollEvent(event))
                {
                        if (event.type == sf::Event::Closed)
                                window.close();
                }
               
                if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right) && testCursor.shape.getPosition().x < testLayer.width * TILESIZE - TILESIZE)
                {
                        if (!rightPressed)
                        {
                                testCursor.shape.move(TILESIZE, 0);
                               
                                /*
                                This is where I'm having the issues, when uncommented, these lines cause a ton of slowdown.

                                testPath.setPath(testLayer.getTileVector()[5][5], testLayer.getTileVector()[(testCursor.shape.getPosition().x / TILESIZE)][(testCursor.shape.getPosition().y / TILESIZE)]);
                                path = testPath.findPath(testLayer);
                                */)

                                rightPressed = true;
                        }
                }
                else
                {
                        rightPressed = false;
                }
               
                for (auto &pathTile : path)
                {
                        pathTile.getShape().setFillColor(sf::Color(255,0,0,128));
                        window.draw(pathTile.getShape());
                }

                testLayer.drawLayer(window);
                testCursor.drawCursor(window);

                window.display();
        }
        return 0;
}
 

And this is the actual pathfinding class:

#include "Path.h"


Path::Path(Tile givenOrigin, Tile givenDestination)
{
        origin = givenOrigin;
        destination = givenDestination;
}


void Path::setPath(Tile givenOrigin, Tile givenDestination){
        origin = givenOrigin;
        destination = givenDestination;
}


std::vector<Tile> Path::findPath(Layer& movementLayer){
        adjacentTilesVector = movementLayer.getAdjacent(origin.getShape().getPosition().x / 32, origin.getShape().getPosition().y / 32);
        closedList.clear();
        //do
        for (int i = 0; i < 10; i++)
        {
                for (auto &adjacent : adjacentTilesVector)
                {
                        openList.push_back(adjacent);
                }

                for (auto &openTile : openList)
                {
                        openTile.pathScore = ComputeScore(openTile, destination);
                        if (openTile.pathScore < lowestScore)
                        {
                                lowestScore = openTile.pathScore;
                                lowestTile = openTile;
                        }
                }

                adjacentTilesVector = movementLayer.getAdjacent(lowestTile.getShape().getPosition().x / 32, lowestTile.getShape().getPosition().y / 32); //This line slows things down.

                closedList.push_back(lowestTile);
                openList.clear();
        } //while (closedList.back().getShape().getPosition() != destination.getShape().getPosition());
        return closedList;
}


int Path::ComputeScore(Tile scoreOrigin, Tile scoreTarget){
        int score;
        int tempy = ((scoreTarget.getShape().getPosition().y / TILESIZE) - (scoreOrigin.getShape().getPosition().y / TILESIZE));
        int tempx = ((scoreTarget.getShape().getPosition().x / TILESIZE) - (scoreOrigin.getShape().getPosition().x / TILESIZE));
        score = (abs(tempy) + abs(tempx));
        return score;
}

Thanks a ton for even just reading this far. I know it's pretty long ^^;
And thanks in advance for any help I get.

Edit: I forgot to add these bits of code.
Here's the getAdjacent function:

std::vector<Tile> Layer::getAdjacent(int x, int y)
{
    std::vector <Tile> adjacentTiles;
    if (y < height -1){
        adjacentTiles.push_back(tileVector[x][y + 1]);
    }
    if (y > 0){
        adjacentTiles.push_back(tileVector[x][y - 1]);
    }
    if (x < width - 1){
        adjacentTiles.push_back(tileVector[x + 1][y]);
    }
    if (x > 0){
        adjacentTiles.push_back(tileVector[x - 1][y]);
    }


    return adjacentTiles;
}

And here's get getShape:

sf::RectangleShape& Tile::getShape()
{
    return shape;
}

2

Graphics / Crash with 2D array of RectangleShapes

« on: October 18, 2014, 09:02:37 am »

Hi folks,
I'm having an issue using a 2D array of RectangleShapes. This is based off some of the code in a tutorial, it's meant to create a bunch of RectangleShapes, give them textures and then draw them. For some reason, when the number of tiles (and so the number of rectangleShapes) gets to a certain number, it starts crashing. The debugger says 'Segmentation Fault'. I've been going over my textbooks and a bunch of forum posts but I can't figure it out. Hopefully it's just something silly I forgot.
Has anyone else had experience with this sort of thing? And more generally, is this the 'correct' way to be doing tiled maps? Is there some other way that's more efficient or easier?
Thanks for your time.

#include <SFML/Graphics.hpp>
#include <iostream>
using namespace sf;
using namespace std;

const int TILE_NUMBER_X = 83; //The code works if these two are set to 82.
const int TILE_NUMBER_Y = 83;
const int TILESIZE = 32;
int main()
{
    Texture tileset;
    tileset.loadFromFile("C:/tileset.png");

    RenderWindow window(sf::VideoMode(800, 800), "SFML works!");
    RectangleShape shapes[TILE_NUMBER_X][TILE_NUMBER_Y];


    for (int y = 0; y < (TILE_NUMBER_X); y++)
    {
        for (int x = 0; x < (TILE_NUMBER_Y); x++)
        {
            shapes[x][y].setSize(Vector2f(TILESIZE, TILESIZE));
            shapes[x][y].setPosition(x * TILESIZE, y* TILESIZE);
            shapes[x][y].setTexture(&tileset);
            shapes[x][y].setTextureRect(IntRect(32,32, 32, 32)); //This normally reads from an .tmx file.
        }
    }

    while (window.isOpen())
    {
        Event event;
        while (window.pollEvent(event))
        {
            if (event.type == Event::Closed)
                window.close();
        }

        window.clear();
       (for (int x = 0; x < (TILE_NUMBER_X); x++)
        {
            for (int y = 0; y < (TILE_NUMBER_Y); y++)
                {
                    window.draw(shapes[x][y]);
                }
        }
        window.display();
    }


    return 0;
}
 

Oh, I meant to post this in graphics. Sorry about that.