Messages

1

Python / SOLVED: I get segmentation fault when inheriting Drawable and trying to draw

« on: February 24, 2014, 04:05:09 pm »

Just needed to add following to Entity constructor. (why does it work on Windows even without?)

    def __init__(self):
        sf.Drawable.__init__(self)
 

The following code works fine on windows machine, but I get segfault when trying to get it run on Arch Linux.
Am I doing something wrong or why does this happen?

import random
import sfml as sf


width = 1280
height = 720


class Entity(sf.Drawable):


        def __init__(self, position):

                self.shape = sf.CircleShape()
                self.shape.radius = 20

                r = 55 + random.randrange(200)
                g = 55 + random.randrange(200)
                b = 55 + random.randrange(200)
                self.shape.fill_color = sf.Color(r, g, b, 50)
                self.shape.outline_color = sf.Color(r, g, b, 200)
                self.shape.outline_thickness = 1

                self.position = position


        # segmentation fault (core dumped)
        def draw(self, target, states):

                self.shape.position = self.position - self.shape.radius
                target.draw(self.shape, states)


        # works fine
        def draw_this(self, target):

                self.shape.position = self.position - self.shape.radius
                target.draw(self.shape)



class Test(object):


        def __init__(self):

                self.window = sf.RenderWindow(sf.VideoMode(width, height), "Render Test")
                self.window.vertical_synchronization = False
                self.entities = []


        def run(self):

                for i in range(20):
                        self.entities.append(Entity(sf.Vector2(
                                random.randrange(width),
                                random.randrange(height))))

                while self.window.is_open:

                        for event in self.window.events:
                                if (type(event) is sf.CloseEvent):
                                        self.window.close()

                        self.render()


        def render(self):

                self.window.clear()

                for e in self.entities:
                        self.window.draw(e)
                        # e.draw_this(self.window)

                self.window.display()



if __name__ == "__main__":

        test = Test()
        test.run()
 

2

General / Re: Integrating pathfinding to the world and scenegraph

« on: December 22, 2013, 06:07:30 pm »

This is currently my biggest problem, mistakes take time and that's what I lack the most. I can't allocate more than one day for implementing path finding. Thus I would like to get it working with one or two tries.

One day severly limits what you can achieve with path finding. It's a very complex topic, especially when you want realistic and continuous results. First, you need to learn the basics of graph theory, and then you need a working implementation. I suggest you use the LEMON library, it has a very modern and powerful API.

I'll look into that, looks interesting.

Generally, path finding consists of multiple steps. Initially, you approximate the walkable world as a graph. Either you simply use waypoints, or something more elaborate like navigation meshes. Then, every time you search a path, you do the following:

• For a given start and end position, find the nearest graph nodes
• Perform a graph search (e.g. A* or Dijkstra)

I have already djikstra and A* implemented (I'll propably go with just A*) and I'm quite familiar with those, but I don't really know how should I integrate those into my world and update nodes when world changes.

[/list]

3

General / Re: Integrating pathfinding to the world and scenegraph

« on: December 21, 2013, 10:08:22 pm »

You answer a lot of design questions about how to integrate something specific into the book's structure. There has recently been a lot of discussion concerning the integration of collision detection and steering behaviors, many of the points still apply here. Some of your questions are also about pathfinding in general, you should probably read some theory about how problems such as moving entities are typically handled (there are tons of very useful blog posts about this topic).

If you could point me towards some usefull blog posts or tutorial on this subject, those would be very helpfull.
For example this helped tremendously when I was writing Collision Grid http://www.metanetsoftware.com/technique/tutorialB.html

Two ideas that I currently have for updating pathfinding nodes:
(1) Add every pathfinding node into my collision grid and check every update if they collide with anything that affects pathfinding and update those nodes accordingly.
(2) Build pathfinding nodes separately and change node status every time tile is added or removed from their position.

And only idea that I have for actually doing the pathfinding:
- For each entity that needs to get somewhere find new path every update since end point is most likely moving and map is changing.

I suggest instead of planning every slightest detail in advance, you sketch up a possible design, begin to implement it and learn from the problems. You will automatically get experience, so that you can refactor things, and design differently next time. Don't be afraid of making mistakes

This is currently my biggest problem, mistakes take time and that's what I lack the most. I can't allocate more than one day for implementing path finding. Thus I would like to get it working with one or two tries.

4

General / Re: Integrating pathfinding to the world and scenegraph

« on: December 21, 2013, 01:53:10 am »

Any ideas what would be a good way to do this?

5

General / Integrating pathfinding to the world and scenegraph

« on: December 19, 2013, 05:21:04 am »

Now that I've got my collision handling working (and components dependant on that) quite well, it's time to move to next problem.

How should I integrate pathfinding in to the book structure?

When and how should I update pathfinding?
How often should I update pathfinding for moving entities?

How does my pathfinding know what entities are placed on the map?

One idea I had was to set pathfinding nodes to my collisiongrid and check nodes to see if they collide with anything and change their characteristics based on that.

Example map:
Start and goal location for 2 entities
###################################
# start   ooo                 end #
#  x      ooo                  x  #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#         ooo                     #
#  oooooooooo                     #
#  oooooooooo                     #
#  oooooooooo                     #
#                                 #
###################################

Entity 1 can dig slowly through (o) wall while Entity 2 cannot
###################################
# start   ooo                 end #
#  x 1________________________ x  #
# 2       ooo           /         #
# |       ooo          /          #
# |       ooo         /           #
# |       ooo        /            #
# |       ooo       /             #
# |       ooo      /              #
# |       ooo     /               #
# |       ooo    /                #
# |oooooooooo   /                 #
# |oooooooooo  /                  #
# |oooooooooo /                   #
# \ _________/                    #
###################################

Pathfinding nodes and entity pathfinding should be updated so Entity 2 can see that shorter path has appeared
###################################
# start   ooo                 end #
#  x...../__1_________________ x  #
# .      |ooo                     #
# .     / ooo                     #
# .    /  ooo                     #
# .   /   ooo                     #
# .  /    ooo                     #
# . /     ooo                     #
# ./      ooo                     #
# /       ooo                     #
# |oooooooooo                     #
# 2oooooooooo                     #
#  oooooooooo                     #
#                                 #
###################################
 

And my current collision detection

#include <CollisionGrid.hpp>

#include <SFML/System/Vector2.hpp>
#include <SFML/System/Time.hpp>

#include <vector>

class Entity;
class CommandQueue;

class Collision
{
        public:
                typedef std::pair<Entity*, Entity*> Pair;

        public:
                                                                                        Collision();
                void                                                            update(sf::Time dt);
                void                                                            updateCollisionGrid(CommandQueue& commands);

        private:
                void                                                            handleCollision(Pair colliders, sf::Vector2f offset, sf::Time dt);

        private:
                CollisionGrid                                           mCollisionGrid;
                std::vector<Entity*>                            mMovingEntities;
};

#include <SFML/System/Vector2.hpp>

#include <map>
#include <set>
#include <vector>


class Entity;

class Cell
{
        public:
                typedef std::set<Entity*> Container;

        public:
                void                            setNeighbours(Cell* left, Cell* right, Cell* up, Cell* down);
                void                            addEntity(Entity& entity);
                void                            removeEntity(Entity& entity);
                Container                       getNearbyEntities();
                void                            clear();

        private:
                void                            appendEntitiesTo(Container& entities) const;

        private:
                Container                       mEntities;

        protected:
                Cell*                           mLeft;
                Cell*                           mRight;
                Cell*                           mUp;
                Cell*                           mDown;
};

class CollisionGrid
{
        public:
                                                        CollisionGrid(float sceneWidth, float sceneHeight, float cellSize);

                void                            addEntity(Entity& entity);
                void                            removeEntity(Entity& entity);
                Cell::Container         getNearbyEntities(Entity& entity);
                void                            clear();

        private:
                Cell&                           getCell(const sf::Vector2f position);

        private:
                std::vector<Cell>       mCells;
                int                                     mCols;
                int                                     mRows;

                float                           mSceneWidth;
                float                           mSceneHeight;
                float                           mCellSize;
};

6

General / Attack implementation from the book: 4 projectiles instead of 1

« on: December 17, 2013, 05:44:44 pm »

Fixed now. I had a typo in my scenenode categories.

Everytime any character pushes attackCommand to the commandqueue, that command gets executed 4 times.
3 projectiles are added where character is currently and 4. as an invisible child to the character. And if I enable players text node, 5th one is added relative to that.  What could cause this?

Category changes behaviour, but I still haven't completely understood the command structure.


Attack command

mAttackCommand.category = Category::Scene;
mAttackCommand.action = [this, &textures] (SceneNode& node, sf::Time)
{
        std::cout << "  -> create projectile" << std::endl;
        createProjectile(node, textures);
};

void Character::createProjectile(SceneNode& node, const TextureHolder& textures) const
{
        std::unique_ptr<Projectile> projectile(new Projectile(Projectile::Placeholder, textures));

        projectile->setPosition(getPosition());
        node.attachChild(std::move(projectile));
}
 

Character update

void Character::updateCurrent(sf::Time dt, CommandQueue& commands)
{
        if (getCategory() == Category::Player)
                updateTexts();

        checkAttackCooldown(dt, commands);
        Entity::updateCurrent(dt, commands);
}

void Character::checkAttackCooldown(sf::Time dt, CommandQueue& commands)
{
        if (getCategory() & Category::Enemy)
                attack();

        // Check for automatic attacking, allow only in intervals
        if (mIsAttacking && mAttackCooldown <= sf::Time::Zero)
        {
                std::cout << "push attack command" << std::endl;
                // Interval expired: Attack
                commands.push(mAttackCommand);
                mAttackCooldown += Table[mType].attackInterval;
                mIsAttacking = false;
        }
        else if (mAttackCooldown > sf::Time::Zero)
        {
                // Interval not expired: Decrease it further
                mAttackCooldown -= dt;
                mIsAttacking = false;
        }
}
 

stdout

push attack command
        -> create projectile
        -> create projectile
        -> create projectile
        -> create projectile
        -> create projectile

7

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 15, 2013, 02:36:05 pm »

I've quickly tested your code, it seems to work well... Does it do what you expect?

Yes, it does and that's the sort of collision I want between pushable entities and walls (and it works with pairs quite well):
wall <-> pushable: pushable can't move inside wall
pushable <-> pushable: both are repelled from each others so they won't collide


So I used your first idea since I've been thinking that too and it seems to do just what I want (very heavy and unoptimized though)

So next steps are to make collision handling run faster and implement some sort of collision grid to bring number of collision checks down.

#include <SFML/Graphics.hpp>
#include <iostream>

const sf::Vector2f entitySize(16.f, 16.f);

bool isMovingUp = false;
bool isMovingDown = false;
bool isMovingRight = false;
bool isMovingLeft = false;

enum Category
{
        wall,
        pushable,
        passable,
};

class Entity
{
        public:
                Entity(sf::Vector2f position, sf::Color color, Category type) : position(position), type(type)
                {
                        shape.setSize(entitySize);
                        shape.setFillColor(sf::Color::Transparent);
                        shape.setOutlineColor(color);
                        shape.setOutlineThickness(1.f);
                }

                sf::Vector2f position;
                sf::Vector2f velocity;
                sf::Vector2f adjustedVelocity;
                sf::Vector2f defaultVelocity;
                sf::RectangleShape shape;
                Category type;
};

void DrawEntity(sf::RenderWindow& window, Entity& entity)
{
        entity.shape.setPosition(entity.position - entity.shape.getSize() / 2.f);
        window.draw(entity.shape);
}

sf::FloatRect GetBoundingRect(const Entity& entity)
{
        return sf::FloatRect(entity.position+entity.velocity - entitySize / 2.f, entitySize);
}

void HandleCollision(std::vector<Entity>& entities)
{
        bool allCollisionsChecked = false;

        while(!allCollisionsChecked)
        {
                allCollisionsChecked = true;
               
                // Pair all possible combinations, but only once per pair
                for (auto first = entities.begin(); first != entities.end(); ++first)
                {
                        for (auto second = std::next(first); second != entities.end(); ++second)
                        {
                                if (first->type == Category::passable || second->type == Category::passable || first->type == Category::wall && second->type == Category::wall)
                                        continue;

                                sf::FloatRect intersection;
                                if (GetBoundingRect(*first).intersects(GetBoundingRect(*second), intersection))
                                {
                                        if (second->position == first->position)
                                                second->position.x += entitySize.x;

                                        sf::Vector2f direction = second->position - first->position;
                                        sf::Vector2f offset;

                                        // X collision
                                        if (abs(direction.x) > abs(direction.y))
                                                offset.x = ((direction.x<0)?-1:1)*intersection.width;

                                        // Y collision
                                        if (abs(direction.x) < abs(direction.y))
                                                offset.y = ((direction.y<0)?-1:1)*intersection.height;

                                        if(first->type == Category::pushable && second->type == Category::pushable)
                                        {
                                                first->velocity -= offset / 2.f;
                                                second->velocity += offset / 2.f;
                                                allCollisionsChecked = false;
                                        }
                                        else if(first->type == Category::pushable)
                                        {
                                                first->velocity -= offset;
                                                allCollisionsChecked = false;
                                        }
                                        else if(second->type == Category::pushable)
                                        {
                                                second->velocity += offset;
                                                allCollisionsChecked = false;
                                        }
                                }
                        }
                }
        }
}

void handlePlayerInput(sf::Keyboard::Key key, bool isPressed)
{
        switch(key)
        {
        case sf::Keyboard::Up:
                isMovingUp = isPressed;
                break;
        case sf::Keyboard::Down:
                isMovingDown = isPressed;
                break;
        case sf::Keyboard::Left:
                isMovingLeft = isPressed;
                break;
        case sf::Keyboard::Right:
                isMovingRight = isPressed;
                break;
        }
}

int main()
{
        sf::RenderWindow window(sf::VideoMode(1280, 720), "SFML Application");
        window.setVerticalSyncEnabled(true);

        std::vector<Entity> entities;

        Entity player(sf::Vector2f(1280/2, 720/2), sf::Color::Green, Category::pushable);
        entities.push_back(player);

        size_t cols = 1280/int(entitySize.x);
        size_t rows = 720/int(entitySize.y);

        size_t i = 0;
        for (; i < cols*rows; ++i)
                if (i%cols == rows/5 && i/cols > rows/6 && i/cols < rows*5/6 || i%cols >= rows/5 && i%cols <= rows*4/5 && (i/cols == rows/6 || i/cols == rows*5/6))
                        entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Yellow, Category::wall));
                //else
                        //entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Transparent, Category::passable));

        while (window.isOpen())
        {
                sf::Event event;
                while (window.pollEvent(event))
                {
                        if (event.type == sf::Event::MouseButtonPressed)
                        {
                                sf::Vector2i pixel(event.mouseButton.x, event.mouseButton.y);
                                sf::Vector2f coord = window.mapPixelToCoords(pixel);

                                if (event.mouseButton.button == sf::Mouse::Left)
                                {
                                        Entity pushable(coord, sf::Color::Blue, Category::pushable);
                                        entities.push_back(pushable);
                                }
                                else if (event.mouseButton.button == sf::Mouse::Right)
                                {
                                        Entity wall(coord, sf::Color::Yellow, Category::wall);
                                        entities.push_back(wall);
                                }
                                else if (event.mouseButton.button == sf::Mouse::Middle)
                                {
                                        Entity mover(coord, sf::Color::Magenta, Category::pushable);
                                        mover.defaultVelocity.x = -1.f;
                                        entities.push_back(mover);
                                }
                        }

                        switch (event.type)
                        {
                                case sf::Event::KeyPressed:
                                        handlePlayerInput(event.key.code, true);
                                        break;

                                case sf::Event::KeyReleased:
                                        handlePlayerInput(event.key.code, false);
                                        break;

                                case sf::Event::Closed:
                                        window.close();
                                        break;
                        }
                }

                if (isMovingUp)
                        entities[0].velocity.y -= 5.f;
                if (isMovingDown)
                        entities[0].velocity.y += 5.f;
                if (isMovingLeft)
                        entities[0].velocity.x -= 5.f;
                if (isMovingRight)
                        entities[0].velocity.x += 5.f;

                if (entities[0].velocity.x != 0.f && entities[0].velocity.y != 0.f)
                {
                        entities[0].velocity.x /= std::sqrt(2.f);
                        entities[0].velocity.y /= std::sqrt(2.f);
                }

                HandleCollision(entities);

                // Apply and reset velocities
                for (Entity& e : entities)
                {
                        e.position += e.velocity;
                        e.velocity = e.defaultVelocity;
                }

                // Draw
                window.clear();
                for (Entity& e : entities)
                        DrawEntity(window, e);
                window.display();
        }
}

It takes quite a many collision checks to fix even simple collision this way

Start, 3 entities:

Velocities in the beginning:
0, 0, <-10
Collisions: 2&3
If entity velocity is changed due the collision do new check

After 1. collision check:
0, <-5, <-5
Collisions: 1&2

After 2. collision check:
<-2.5, <-2.5, <-5
Collisions: 2&3

After 3. collision check:
<-2.5, <-3.75, <-3.75
Collisions: 1&2

After 4. collision check:
<-3.125, <-3.125, <-3.75
Collisions: 2&3

After nth collision check:
<-3.33, <-3.33, <-3.33
No collisions

8

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 15, 2013, 06:08:28 am »

You can click on the screen to insert a new entity. Collisions will be resolved over multiple frames, and symmetrically. The collision response is not perfect; you'll see some shivers when many entities overlap in a large area, and entities with identical positions are left unchanged. But overall, collision is resolved in a not so unintuitive way. I'm sure you can tweak this more and smooth it according to your needs

I had little time today in my hands so I tried your approach. Overall it works quite nicely with few entities.

Entity, velocity and boundingRect:


Collision response:

If colliding with wall, push pushable entity away.
Or if colliding with other pushable entity, push both.
Skip wall<->wall collision checks and checks with passable terrain.

While single collisions and collisions with just few entities work quite nicely, problems arise when adding multiple pushable and especially moving entities to the world.

Multiple moving entities can push other entities through walls and pushable entities can be squeezed together.

What causes the problem (numbers below are velocity modifications due the collision handling):

At the beginning leftmost and middle entities are not colliding with each others, but after rightmost entity collides with middle one, the velocity middle entity gains now causes it to collide with leftmost one

How it should be:

Or if the leftmost entity was a wall -> 0, 0, -v
But I don't really know (or atleast good ideas) how to achieve this.

Sample code below:
Arrow keys: move green entity
Left mouse button: spawn pushable entities
Right mouse button: spawn wall entities
Middle mouse button: spawn moving pushable entities

#include <SFML/Graphics.hpp>
#include <iostream>

const sf::Vector2f entitySize(16.f, 16.f);

bool isMovingUp = false;
bool isMovingDown = false;
bool isMovingRight = false;
bool isMovingLeft = false;

enum Category
{
        wall,
        pushable,
        passable,
};

class Entity
{
        public:
                Entity(sf::Vector2f position, sf::Color color, Category type) : position(position), type(type)
                {
                        shape.setSize(entitySize);
                        shape.setFillColor(color);
                }

                sf::Vector2f position;
                sf::Vector2f velocity;
                sf::Vector2f adjustedVelocity;
                sf::Vector2f defaultVelocity;
                sf::RectangleShape shape;
                Category type;
};

void DrawEntity(sf::RenderWindow& window, Entity& entity)
{
        entity.shape.setPosition(entity.position - entity.shape.getSize() / 2.f);
        window.draw(entity.shape);
}

sf::FloatRect GetBoundingRect(const Entity& entity)
{
        sf::Vector2f topLeftCorner;
        sf::Vector2f size(entitySize.x + abs(entity.velocity.x), entitySize.y + abs(entity.velocity.y));

        if (entity.velocity.x < 0)
                topLeftCorner.x = entity.velocity.x;

        if (entity.velocity.y < 0)
                topLeftCorner.y = entity.velocity.y;

        return sf::FloatRect(entity.position+topLeftCorner - entitySize / 2.f, size);
}

void HandleCollision(std::vector<Entity>& entities)
{
        // Pair all possible combinations, but only once per pair
        for (auto first = entities.begin(); first != entities.end(); ++first)
        {
                for (auto second = std::next(first); second != entities.end(); ++second)
                {
                        if (first->type == Category::passable || second->type == Category::passable || first->type == Category::wall && second->type == Category::wall)
                                continue;

                        sf::FloatRect intersection;
                        if (GetBoundingRect(*first).intersects(GetBoundingRect(*second), intersection))
                        {
                                sf::Vector2f direction = second->position - first->position;
                                sf::Vector2f offset;

                                // X collision
                                if (abs(direction.x) > abs(direction.y))
                                        offset.x = ((direction.x<0)?-1:1)*intersection.width;

                                // Y collision
                                if (abs(direction.x) < abs(direction.y))
                                        offset.y = ((direction.y<0)?-1:1)*intersection.height;

                                if(first->type == Category::pushable && second->type == Category::pushable)
                                {
                                        first->velocity -= offset / 2.f;
                                        second->velocity += offset / 2.f;
                                }
                                else if(first->type == Category::pushable)
                                {
                                        first->velocity -= offset;
                                }
                                else if(second->type == Category::pushable)
                                {
                                        second->velocity += offset;
                                }
                        }
                }
        }
}

void handlePlayerInput(sf::Keyboard::Key key, bool isPressed)
{
        switch(key)
        {
        case sf::Keyboard::Up:
                isMovingUp = isPressed;
                break;
        case sf::Keyboard::Down:
                isMovingDown = isPressed;
                break;
        case sf::Keyboard::Left:
                isMovingLeft = isPressed;
                break;
        case sf::Keyboard::Right:
                isMovingRight = isPressed;
                break;
        }
}

int main()
{
        sf::RenderWindow window(sf::VideoMode(1280, 720), "SFML Application");
        window.setVerticalSyncEnabled(true);

        std::vector<Entity> entities;

        Entity player(sf::Vector2f(1280/2, 720/2), sf::Color::Green, Category::pushable);
        entities.push_back(player);

        size_t cols = 1280/int(entitySize.x);
        size_t rows = 720/int(entitySize.y);

        size_t i = 0;
        for (; i < cols*rows; ++i)
                if (i%cols == rows/5 && i/cols > rows/6 && i/cols < rows*5/6 || i%cols >= rows/5 && i%cols <= rows*4/5 && (i/cols == rows/6 || i/cols == rows*5/6))
                        entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Yellow, Category::wall));
                //else
                        //entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Transparent, Category::passable));

        while (window.isOpen())
        {
                sf::Event event;
                while (window.pollEvent(event))
                {
                        if (event.type == sf::Event::MouseButtonPressed)
                        {
                                sf::Vector2i pixel(event.mouseButton.x, event.mouseButton.y);
                                sf::Vector2f coord = window.mapPixelToCoords(pixel);

                                if (event.mouseButton.button == sf::Mouse::Left)
                                {
                                        Entity pushable(coord, sf::Color::Blue, Category::pushable);
                                        entities.push_back(pushable);
                                }
                                else if (event.mouseButton.button == sf::Mouse::Right)
                                {
                                        Entity wall(coord, sf::Color::Yellow, Category::wall);
                                        entities.push_back(wall);
                                }
                                else if (event.mouseButton.button == sf::Mouse::Middle)
                                {
                                        Entity mover(coord, sf::Color::Magenta, Category::pushable);
                                        mover.defaultVelocity.x = -1.f;
                                        entities.push_back(mover);
                                }
                        }

                        switch (event.type)
                        {
                                case sf::Event::KeyPressed:
                                        handlePlayerInput(event.key.code, true);
                                        break;

                                case sf::Event::KeyReleased:
                                        handlePlayerInput(event.key.code, false);
                                        break;

                                case sf::Event::Closed:
                                        window.close();
                                        break;
                        }
                }

                if (isMovingUp)
                        entities[0].velocity.y -= 5.f;
                if (isMovingDown)
                        entities[0].velocity.y += 5.f;
                if (isMovingLeft)
                        entities[0].velocity.x -= 5.f;
                if (isMovingRight)
                        entities[0].velocity.x += 5.f;

                if (entities[0].velocity.x != 0.f && entities[0].velocity.y != 0.f)
                {
                        entities[0].velocity.x /= std::sqrt(2.f);
                        entities[0].velocity.y /= std::sqrt(2.f);
                }

                HandleCollision(entities);

                // Apply and reset velocities
                for (Entity& e : entities)
                {
                        e.position += e.velocity;
                        e.velocity = e.defaultVelocity;
                }

                // Draw
                window.clear();
                for (Entity& e : entities)
                        DrawEntity(window, e);
                window.display();
        }
}

9

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 12, 2013, 01:18:58 am »

I still think the separate X/Y movement for collision response is quite complicated to implement. It might be worthwhile to try a different approach, I mentioned the vector that leads away from the colliding entity. The idea is that all colliding entities contribute to the total "evade" vector. This approach is very simple, it took me only about ten minutes to write a short program that illustrates the principle.

Thank you for your 10 minutes
I'll look into it.

10

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 11, 2013, 10:42:25 pm »

So we would handle collision and movement separately?

Yes... That's what I'm saying all the time.

The movement depends on the velocity, and the velocity can be affected by collision response. Thus, the collision response indirectly influences the movement.

Something like this?

** Start **
Entities (all entities are non passable):
1, 2, 3,
4, 5, 6,
7, 8, 9


** Move everything **
Blue entities move towards green entity and green entity moves to the down right



** Check collisions **
List of collisions (let's handle collisions in this order:
1: E2 collision with E3 (X collision)
2: E4 collision with E7 (Y collision)
3: E5 collision with E6 (X collision)
4: E5 collision with E8 (Y collision)
5: E6 collision with E8 (X and Y collision)

** Handle collisions **
1: reset E2 and E3 X movement to prevent collision

   -> E2 collides now with E1 (X collision)

2: reset E4 and E7 Y movement to prevent collision

   -> E4 collides now with E1 (Y collision)

3: reset E5 and E6 X movement to prevent collision

   -> E5 collides now with E4 (X collision)
   -> E5 collides now with E7 (Y collision)
   -> E5 collides now with E8 (X and Y collision)

4: reset E5 and E8 Y movement to prevent collision

   -> E5 collides now with E1 (X and Y collision)
   -> E5 collides now with E2 (Y collision)
   -> E5 collides now with E4 (X collision)

5: reset E6 and E8 X or Y collision to prevent collision (I've yet to figure out which one) (let's select X collision this time)

   -> E8 collides with E7 (X collision)


** Check collisions **
1: E1 collision with E2 (X)
2: E1 collision with E4 (Y)
3: E1 collision with E5 (X and Y)
4: E2 collision with E4 (X and Y)
5: E2 collision with E5 (Y)
6: E4 collision with E5 (X)
7: E7 collision with E8 (X)

** Handle collisions **
1: reset E1 X movement (E2 movement already resetted)
2: reset E1 Y movement (E4 movement already resetted)
3: Do nothing (E1 and E5 movement already resetted)
4: reset E2 Y movement
5: Do nothing
6: reset E4 X movement
7: reset E7 X movement



** Check collisions **
No more collision
   -> Continue



Problems I have with above aproach:
1. hard to detect should I reset X or Y movement

Scenario 1
Entities:

B1
B2, G

Blue entities move towards green entity, while green entity moves top left

**Collisions**
1: B1 collides with B2 (Y)
2: B1 collides with G (X and Y)
3: B2 collides with G (X)

-> Reset blue movement
-> Reset green X movement (nothing blocks Y)

Scenario 2
Entities:

B1, B2
    G

Blue entities move towards green entity, while green entity moves top left

**Collisions**
1: B1 collides with B2 (X)
2: B1 collides with G (X and Y)
3: B2 collides with G (Y)

-> Reset blue movement
-> Reset green Y movement (nothing blocks X)

Collisions don't know about each others and in these scenarios 2. collision is fixed by handling 3. collision.
How should I handle XY-collision?

Another reason why it's a bad idea to handle collision during Entity::current() is the asymmetry created by the order of iteration: Entities that are moved before others (but in the same frame) get priority for collision. When an entity checks other entities for collision, a part of them has already moved, while another one hasn't.

But there's still assymmetry depending on which order collisions are handled. (It doesn't really matter in this case though)

The third reason is modularity and separation of responsibilities. It's favorable if Entity needn't be aware of the whole world. As suggested, I would even create a separate class for collision detection and response, because World is already quite big.

This is main reason why I would like to move collision handling away from entity update step. It just makes movement a bit trickier.

11

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 11, 2013, 06:23:43 pm »

What do you mean from outside?

From outside the entity, i.e. in World or a specific collision class.

So we would handle collision and movement separately?

World update

void World::update(sf::Time dt)
{
        // Reset player velocity
        for (Character* c : mPlayers)
                c->setVelocity(0.f, 0.f);

        guideEnemies();

        // Forward commands to scene graph
        while (!mCommandQueue.isEmpty())
                mSceneGraph.onCommand(mCommandQueue.pop(), dt);

        adaptPlayerVelocity();

        spawnEnemies();

        // Regular update step
        mSceneGraph.update(dt, mCommandQueue);

        handleCollisions();
}

But how can my entity know if it can move to some location if it has no access to collision grid and locations of other entities?

void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
        checkIfEntityCanMoveUsingmVelocityAndAdjustAccordingly();
        move(mVelocity * dt.asSeconds());
        // shouldn't I also update collision grid after entity moves?
}

12

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 10, 2013, 12:17:20 am »

Edit: Ah, you mean you want to check immediately after X movement and immediately after Y movement. What you could do: Don't apply the velocity directly. Check from outside if position + velocity would lead to a collision (for both velocity components separately), and react correspondingly. If no collision occurs, apply the velocity. I'm not sure if it's more reasonable to abuse the current Entity::mVelocity attribute or to create a new one, such as Entity::mPlannedVelocity. You could experiment a bit here.

"Check from outside if position + velocity would lead to a collision"
What do you mean from outside? And how would you check that collision? Add new object to the collisiongrid and check if it collides with anyhing and if it doesn't move entity?

13

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 07, 2013, 05:13:34 pm »

It is just a design choice whether you handle collisions centralized in World or in each Entity -- the algorithmic effort remains the same. I suggested World because this class has a view "from outside" and because I wanted to move the responsibility for collision detection and response out of each Entity.

This is what I would also like to do, but I have no idea how to handle collisions that happened due the chain reaction and if collisions happened from X or Y direction or in what order they happened.

I find algorithimc effort lot simpler in
1) move X
2) check collision, if collision resetX
3) move Y
4) check collision, if collision resetY
5) repeat 1-4 for all entities

compared to
1) move all
2) check all collision
3) if collision check X or Y -> reset X or Y -> check collision again (is this world collision or entity collision?)
4) after possible reset check collisions again -> reset other entities
5) repeat 3-4


Is there some other way to move collision handling away from the entities update step while still checking collisions after every X and Y movement?

If the functionality becomes more complex, it may also be worthwhile to create a new class dedicated to collision. Especially since World is already big and has many responsibilities. Where would you store your grid data structure, if not in World (or the new Collision class)? Entity is certainly not the right place for it.

Currently I store collisiongrid in world and pass its reference to the entities.

Implementin grid or quadtree itself is rather trivial, I'm just having problems figuring out how (and when) to use it.

14

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 07, 2013, 03:59:06 pm »

You mean:
1) Move everything
2) Check collisions
?

That seems like a lot more work than checking collisions after each entity move.

More work than what?

More work than checking collisions after each movement in entity-class.

This is what I have currently. I check and handle possible collisions after something have moved.

void World::update(sf::Time dt)
{
        // Reset player velocity
        for (Character* c : mPlayers)
                c->setVelocity(0.f, 0.f);

        guideEnemies();

        // Forward commands to scene graph
        while (!mCommandQueue.isEmpty())
                mSceneGraph.onCommand(mCommandQueue.pop(), dt);

        adaptPlayerVelocity();

        // Regular update step
        mSceneGraph.update(dt, mCommandQueue);
}

void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
        setPreviousPosition(getPosition()); // for resetting after possible collision
        move(sf::Vector2f(mVelocity.x, 0) * dt.asSeconds());
        handleCollision();
        setPreviousPosition(getPosition()); // for resetting after possible collision
        move(sf::Vector2f(0, mVelocity.y) * dt.asSeconds());
        handleCollision();
}

How I uderstood your suggestion. Check and handle collisions after everything has moved.

void World::update(sf::Time dt)
{
        // Reset player velocity
        for (Character* c : mPlayers)
                c->setVelocity(0.f, 0.f);

        guideEnemies();

        // Forward commands to scene graph
        while (!mCommandQueue.isEmpty())
                mSceneGraph.onCommand(mCommandQueue.pop(), dt);

        adaptPlayerVelocity();

        // Regular update step
        mSceneGraph.update(dt, mCommandQueue);
        handleCollisions();
}

void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
        setPreviousPosition(getPosition());
        move(sf::Vector2f(mVelocity.x, mVelocity.y) * dt.asSeconds());
}

You have to check each collidable entity for collision after it has moved -- the trick is to reduce the collision checks to a minimum, for example by keeping them local using a grid.

How I could check collisions from world-class after each entity movement, if that collision check isn't part of entity update step?

15

General / Re: Implementing collision grid or quadtree into sfml book game structure

« on: December 07, 2013, 03:41:06 pm »

But Quadtrees are already quite advanced because of their hierarchical organization, for your purposes it might be enough to have a flat grid of equally-sized cells. For each cell, you would then perform collision detection for entities inside the cell and its neighbors.

I'm currently working on simple grid, since that's most likely enough for me.

In the World update, you perform a search in the quadtree for possible collisions.

You mean:
1) Move everything
2) Check collisions
?

That seems like a lot more work than checking collisions after each entity move. Since having lots of separate X and Y collisions and chainreaction collisions happening at the same time seem rather confusing.