Integrating pathfinding to the world and scenegraph

[warbaque]

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;
};

[warbaque]

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

[Nexus]

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).

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

[warbaque]

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.

[Nexus]

If you could point me towards some usefull blog posts or tutorial on this subject, those would be very helpfull.

It's already some time ago since I've read them, so I don't remember them exactly. But you can use a search engine. It also depends on how much you already know about path finding. If you have never done anything with it, Wikipedia would be a good starting point.

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.

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)
• Transform the path of nodes into a path of positions, exploiting the underlying geometry (for a navmesh, walk along the polygons instead of center nodes)
  
• Smooth the resulting path, possibly introducing shortcuts and direct connections where line-of-sight exists
  

When you limit the movement to 4 or 8 directions on a grid, the problem will become siginificantly simpler: you only need to perform steps 1 and 2.

[warbaque]

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]