xoreos Wiki - User contributions [en]

Pathfinding

2017-05-03T09:22:23Z

Supermanu: /* External libraries */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== General considerations ==
=== 3D vectors ===
Both algorithms extensively use 3D vectors and related operations. Should we use <code>Common::Vector3</code> generally or only when it is really needed and uses arrays for all the other cases?

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A* algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the ''POC'' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The ''SSFA'' is relatively straightforward technically. The main difficulty is about creature's size. In order to take it into account, the ''POC'' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-03T09:19:57Z

Supermanu: /* Show me the code! */ Add general considerations

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== General considerations ==
=== 3D vectors ===
Both algorithms extensively use 3D vectors and related operations. Should we use <code>Common::Vector3</code> generally or only when it is really needed and uses arrays for all the other cases?

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A* algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The ''SSFA'' is relatively straightforward technically. The main difficulty is about creature's size. In order to take it into account, the ''POC'' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:20:23Z

Supermanu: /* Simple Stupid Funnel Algorithm */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A* algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The ''SSFA'' is relatively straightforward technically. The main difficulty is about creature's size. In order to take it into account, the ''POC'' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:19:56Z

Supermanu: /* Simple Stupid Funnel Algorithm */ Fix italic style for POC

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A* algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the ''POC'' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:18:45Z

Supermanu: /* Estimation and heuristic function */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A* algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:16:42Z

Supermanu: /* Creature's size */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A.2A_algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered like in [1].

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:15:31Z

Supermanu: /* A* Algorithm */ Add creature's size check

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A.2A_algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== Creature's size ===
This is an ideal step to check if the creature will fit into the path. In the ''POC'', each face ''A*'' tries to go is naively checked by the size of the crossing edge. If it is too small, a second check is done by looking the intersection between a segment the size of the creature and the faces around. The first check might get false-positive with flat triangles and something else should be considered.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:02:25Z

Supermanu: /* Estimation and heuristic function */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in [[#A.2A_algorithm]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-05-01T20:01:40Z

Supermanu: /* Estimation and heuristic function */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [[#A.2A_algorithm first image]]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

TODO

2017-05-01T11:47:52Z

Supermanu: /* NWN */ Add link to pathfinding page

This is a long rambly list of things left to do in xoreos and xoreos-tools. Anybody is welcome to tackle any of these tasks, but please also read our [[Developer_Central|general contributor overview]], including our [[Code_Formatting_Conventions|Code Formatting Conventions]], [[Commit_Guidelines|Commit Guidelines]] and [https://github.com/xoreos/xoreos/blob/master/CODE_OF_CONDUCT.md Code of Conduct]. If you plan to do any of these tasks, please also [[Contact_us|contact us]] beforehand, so we can better coordinate multiple people interested in doing the same task, and discuss how to best solve the problem. Thanks. :)

('''See also:''' the Kanban-like "Projects" boards on GitHub: https://github.com/orgs/xoreos/projects, but they're not public and no way to make public at the moment. Boo.)

== Documentation ==

=== Developer information ===
* Extend the developer information on the wiki
** Explain how to get the xoreos sources on various platforms
** Expand GNU/Linux compiling instructions to cover more distributions
** Expand Mac OS X compiling instructions
*** Xcode
*** Homebrew/MacPorts/Fink
*** CMake, Libraries
** [http://wiki.arx-libertatis.org/Developer_Information Arx Libertatis] has an extensive dev page
* Document file formats on the wiki?
** Or integrate info into XentaxWiki?
** Both?

=== User information ===
* More user information on the wiki
** How to download xoreos
** How to install the games on various platforms
** [http://wiki.arx-libertatis.org/Main_Page Arx Libertatis] does that pretty well

=== Modder information ===
* Link to relevant modding resources
* Maybe even some kind of Modder's Handbook
** A big overview of modding Aurora games in general
*** Differences and commonalities between games
** Linking/Grouping engine functions between games

== Website ==

=== Design ===
* Better website design?
** It still should be static in the end
*** No PHP or Rails
*** Very light on JavaScript
*** No Flash!
** Maybe a bit more unique, graphical
** For legal reasons, we shouldn't directly use art or designs from the original games
*** Something inspired by the art of the orginal games would fit

=== Octopress ===
* Move away from Octopress?
** Alternative should still produce static HTML somehow
** Octopress works rather well. It reads Markdown, which is a plus
* Octopress 3.0?
** Not finished yet, it seems

== Standalone(ish) fixes/improvements ==

=== Broken NWN2 XML ===
* Not standards-conforming XML. Need custom XML parser; stock XML parsing libraries will just throw errors.
** <nowiki><?xml version="1.0" encoding="NWN2UI"></nowiki>
** No single root element
** Attribute values not enclosed in quotes most of the time
** Special characters in attribute values not properly escaped
** Unmatched quotes on several occasions
* Event functions
* Special values like PARENT_WIDTH
* [https://github.com/xoreos/xoreos-tools/pull/1 Altrite is working on a broken-XML fixer]

=== CJK glyphs in the console ===
* The "system font" we use for our debug console, DejaVu Sans Mono Bold, does not feature any CJK (Chinese, Japanese, Korean) glyphs
* Not strictly necessary, but nice to have for printing, say, Witcher area names in Asian languages
* We could maybe integrate CJK glyphs from the [http://fonts.jp/hanazono/ Hanazono fonts] or other suitable libre fonts
* We need to match the height with DejaVu Sans Mono Bold
* CJK glyphs tend to be more complex and therefore wider. They're usually rendered twice as wide as Latin glyphs
* Our console code needs to take that into account

=== Fuzzing ===
* Run our file readers, image decoders, etc. through a fuzzer, like [http://lcamtuf.coredump.cx/afl/ afl] (american fuzzy lop)
* Fix any cases where it crashes
* The xoreos-tools might be a good starting point for singular, standalone testing
** For image decoders, a slightly modified xoreostex2tga tool might work
* File formats already fuzzed:
** CBGT, CDPTH, DDS, NBFS, NCGR, NCLR, SBM, TGA, TPC, TXB
** 2DA, KEY/BIF, ERF, GFF3, GFF4, GDA, TLK, NSBTX, RIM, SMALL, SSF

=== Script decompiler ===
* It might be quite useful to have a NWScript decompiler in xoreos-tools
* We have a script disassembler, ncsdis
** Which already does code flow analysis
* Missing:
** Code generation
** Collapsing of instruction chains into single-line NWScript code
*** For example, "int var = foo * bar + quux" compiles to a long chain with multiple temporaries
** Proper handling of structs and vectors

=== Script compiler ===
* An NWScript compiler might be useful as well
** A script assembler might be an easy first step

=== File format writers ===
* GFF3Writer, GFF4Writer
** Both necessary to create save games compatible with the original games
** Also useful for a xml2gff tool
* xml2tlk
** TalkTable_GFF::write02() and ::write05()
** Needs GFF4Writer
* Archive (ERF, RIM, KEY/BIF) packers?

=== Config file ===
* Should be more preserving of the layout
** Especially empty lines
** UTF-8 Byte-Order-Mark when using native Windows editors
** \r is currently always stripped. Maybe preserve that too
*** Autodetect when \r is already used, and add it to new config lines too
** This basically needs a complete rewrite of the config parser
*** Don't just look for comments, just throw everything after "foo=bar" into the "comment" variable, including whitespace
*** And all whitespace before "foo=bar" into a "prefix" variable
** Maybe even always add BOM and \r when writing a new config file on Windows?

=== Windows-specific / Wine-specific ===
* When running my mingw32 cross-compiled xoreos EXE in Wine, the menu button texts are partially cut off
** Z-fighting issue?
** Does that also occur on a real Windows?

=== GUI ===
* xoreos could use a global GUI to start games from
* Should probably be similar to ScummVM's GUI, at least in effect
* Should read the config file, list all targets
** Press a "Play" button to play the game
** Press an "Edit" button to edit the entry
*** Dialog options to edit common settings
*** An additional free-form editor?
*** Game-specific options?
** A button to edit global settings ("xoreos" config domain)
** For the future, a way to immediately load a saved game?
** An "Add" button to add a game
*** File browser
**** Select directories for most game
**** Select file for Sonic Chronicles
*** View current saved games of a target?
* Probably implemented using OpenGL, just like, say, the console
* Theme-able/Skinable?
* Some potential stumbling blocks
** Displaying "uncommon" text in both game descriptions and file paths
*** "Decomposed" letters, i.e. base letter + combining glyphs
*** CJK
*** Arabic and other scripts where letters change depending on their place in the word
*** Right-to-left
** Shortening those strings when they don't fit in their fields is also potentially difficult

=== Localization ===
* Text in exceptions?
** At least the user-visible ones, like "Failed to detect game"
** Or maybe we should clean that up and split them into "program logic failure" and "user failure", with only the latter translated
* Strings for the engine loader progress bar
* Debug console string
* GUI (see above) strings
* [http://www.gnu.org/software/gettext/ GNU gettext] would be one solution

=== Unit tests ===
* A lot of the common code would really profit from unit tests
* Automake has [https://www.gnu.org/software/automake/manual/html_node/Tests.html built-in support for test scripts], if that's the way we want to go
* Alternatively, there's [https://en.wikipedia.org/wiki/CppUnit CppUnit]
* And loads of other alternatives

=== Resource Explorer ===
* A portable, user-friendly graphical resource explorer could be useful
* [https://github.com/xoreos/phaethon Phaethon] is a start
** It can look into game archives, show textures and play sounds
** It uses [https://www.wxwidgets.org/ wxWidgets] to do the GUI
** Or possibly rewriting it to use [https://www.qt.io/ Qt] is better?

=== Model converters ===
* Document the model formats
* Convert between the binary model formats and their ASCII equivalents
* Convert between the binary model formats and ones that can be opened by modelling tools
** 3D Studio Max
** Blender

=== Full-fledged modding toolset ===
* Similar to the NWN, NWN2 or Witcher toolset, but portable and FLOSS
** Might also support other games?
* Out of scope for xoreos
** Still, such a thing would be welcome under the xoreos banner
* [http://sourceforge.net/projects/neveredit/ Neveredit] might still be worth a look

== Build system ==

=== CMake ===
* Current doesn't set the git version to "+unk" when git isn't found
* make install?
* make doxygen?

=== Autotools ===
* Suppress the "fatal: not a git repository" when building gitstamp without a git directory
* Increased modularity
** Disabling engines
*** Dropping library dependencies when the still enabled engine don't need them
** Making library dependencies optional (and disabling certain features, then)
*** liblzma is only needed for the iOS version of KotOR
*** libxml2 is only needed for the two Dragon Age games
*** libxvidcore is only needed for the Mac version of KotOR
*** libvorbis/libogg are probably only needed for The Witcher
** When something is disabled, skip it, if possible
*** Like the videos in KotOR Mac
** If skipping is not possible, error out
** We should then show a summary of what is enabled/disabled at the end of the configure script
* Switch to a non-recursive make setup?
** We still want a Makefile.am for each directory, so with include
* Remove the need to list all subdirectories with AC_CONFIG_FILES() in the configure.ac
** Parse Makefile.am for SUBDIRS, recursively?
*** Needs to pick up conditionally added entries, like for glew
** Substitution needs to happen before automake is called!
*** https://stackoverflow.com/questions/18200733/use-shell-commands-to-find-makefile-am-in-configure-ac
*** <nowiki>AC_CONFIG_FILES(m4_esyscmd([find . -name Makefile.am | sed -e 's/^\.\///;s/\.am$//']))</nowiki>

== Nitro ==

* The Nintendo DS (Nitro) specific file formats should probably be moved out of src/aurora/ and into src/nitro
* nitrofile, cdpth, nsbtx, smallfile
** nsbtx needs to be split into a class accessing the textures in src/nitro/ and an archive class on top in src/aurora/
** This means src/aurora/ accesses src/nitro/, so libnitro.la needs to come after libaurora.la in the linking order
* ndsrom as well?
* What about nftrfont and model_sonic in src/graphics/aurora/?
** src/graphics/nitro/?
** This would have src/graphics/nitro/ access src/graphics/aurora/, so graphics/libnitro.la needs to come before graphics/libaurora.la in the linking order
** That would be the other way round than for src/nitro/. Too confusing?

== Graphics ==

=== MDL supermodels and animations ===
* Mostly working in NWN thanks to jbowtie's work
* Might need some cleanup
* Animation scale is off in a lot of cases. Mostly visible in the talking and yawning animations in non-human characters
* Models should smoothly change between different animations
* The animation system probably needs to be a bit more complex, to allow for "overlaying" different animations onto each other. For example, for speaking while holding an object and keeping the head focused on the PC character.

=== Lighting ===
* We don't yet have a proper light system
* I started working on it: [https://drmccoy.de/xoreos/20150809T223407.png], but my approach is seriously lacking. You can see the edges of the tiles that make up on NWN area in many cases ([https://drmccoy.de/xoreos/20150809T223507.png], [https://drmccoy.de/xoreos/20150809T223548.png])
** See the [https://github.com/xoreos/xoreos/tree/light light branch] in the git repository
** Of course, the actual glLight* stuff won't be relevant anymore as soon as shaders are there
** Lighting in several (ASCII?) area tiles is broken
*** The door in Prelude.nwm's "m0q1a" area
*** A water tile in Chapter2.nwm's "map_m2q1a" area
*** A sloped snow tile in XP2_Chapter3.nwm's "thecityoflostsou"

=== Materials ===
* Materials in The Witcher are closely tied to shaders

=== OpenGL and Shaders ===
* mirv_ is currently working on a graphics system overhaul, complete with shader support
* All Aurora games use shaders in some form
* NWN uses ARB shaders. We probably need to rewrite them from scratch
* DirectX shaders might be automatically convertible with Cg?
* Otherwise, look at what Wine does with the shaders, and use that as a basis?
* All the games, even NWN, use some form of shaders. Still totally missing from xoreos, since we have no idea how to use them in general yet. Moreover, this was before GLSL, so they're in the old assembly-like language. We probably need to rewrite them from scratch
* We need shaders for tinting in NWN2 (objects and area geometry) and TexturePaint nodes in Witcher

=== SDL 1.2 ===
* Optionally link against SDL 1.2 instead of SDL 2
* Should ideally use a configure flag to select between the two
** Maybe a CMake flag as well, if possible
* Assigned to clone2727, so anybody interested in this should coordinate with him

== Videos ==

=== XMV/WMV ===
* Used in Xbox versions of KotOR/KotOR2
* Our WMV decoder (for XMV videos used in Xbox versions) is missing P-frames and J-frame
** Code exists in ffmpeg, but is connected to the MPEG-4 family mess

=== Actimagine VX ===
* Used in the Nintendo DS game Sonic Chronicles
* https://wiki.multimedia.cx/index.php?title=Actimagine_Video_Codec

=== Sorenson 3 ===
* One single video in the Mac port of KotOR2, the Aspyr logo, uses the Sorenson 3 codec
** ffmpeg has a decoder, but it's connected to the MPEG-4 family mess (SVQ3 is similar to H.264)
* ScummVM needs that too
** While xoreos is GPLv3+, ScummVM is GPLv2+
** Somebody implementing Sorenson 3 for xoreos should ideally give explicit permission to relicense it GPLv2+ for ScummVM
*** Of course, if the decoder is based on prior work by other people, it has to be compatible with both GPLv2+ and GPLv3+

=== Optimizations ===
* Optimize our simple BitStream interface
** See [https://fgiesen.wordpress.com/2016/01/02/end-of-buffer-checks-in-decompressors/ this blog post]
** Specifically, we don't do any peeking at all
** It still needs to handle different memory layouts, though
* Likewise, our Huffman class could probably be tuned a lot
* Pull in fft/rdft/dct/mdct optimizations from FFmpeg?

== Sound ==

=== FMOD ===
* Dragon Age: Origins uses FMOD for sound and music
* I have experimental FSB (FMOD sound bank) support working in a private branch
* FEV (FMOD events) format is still unknown to us
** Apparently, groups of event lists with events
** Event is everything from "play sound", over "set volume" to "apply echo"
** Game areas specify the group to use for the area
** Scripts then probably tell FMOD to play event lists out of that group

=== Wwise ===
* Dragon Age 2 uses Wwise for sound and music
* Should be similar in concept to FMD

== Events ==

=== Gamepad binding ===
* The Xbox versions of KotOR and KotOR2 don't use a mouse. We have basic support for joysticks/gamepads, but no real bindings to the engine or ideas how to handle that in general
* We might want to handle the controller support the new KotOR2 Steam update brought
** override folder contains a gamepad.txt then
* Also hack in controller support for a non-Steam KotOR2? And for KotOR?
* Controller support in Jade Empire
* Controller support for Sonic? It is a Nintendo DS game after all
* Controller support for the non-console versions of the Dragon Age games?

== Network ==
* We need a network subsystem
** [https://www.libsdl.org/projects/SDL_net/ SDL_net]?
** [http://www.boost.org/doc/libs/release/libs/asio/ Boost.Asio]?
** More options here: http://stackoverflow.com/questions/118945/best-c-c-network-library
* Engines need to be split into client and server classes
** The original engines all still do that, even when not exposing anything to users
** NWN and NWN2 allow user multiplayer

== Engines ==

=== Script system ===
* ImperatorPrime had started on a script system rewrite
** Includes functions with real signatures
** Maybe switch to that, if it works
* Rounds, object heartbeat scripts
* KotOR2 and NWN2 have some extensions
** It seems like they don't need any extensions to the low-level bytecode stuff
* Witcher uses Lua scripts together with NWScript
* Sonic has no scripts at all, it seems
* Currently a script in an infinite loop locks the game thread
** Timeout? Asynchronous script execution?

=== NWN ===
* Menus
** Basics are there, but needs fleshing out
** Supermanu is working on the character generator
* [[Pathfinding]], walkmesh
** "Moving" should move the PC, not the camera
** NPC walking
** Triggers, areas on the floor that calls scripts on enter/leave
* Models
** ASCII models need averaging of smooth group normals
* NWN objects need an inventory concept
** Player characters' might be different
*** Inventory tetris
*** Inventory item icons
* Multi-page asian fonts
* LanguageID 0 is not necessarily "English", but "The language of the game install"
** This is okay for languages with Latin characters
** Messes up strings in community modules with Asian languages that stuff strings in to languageID 0
** The original fails there too, though

=== KotOR/KotOR2 ===
* Menus
** Basic structure is already there, just missing most of the specific widgets stuff
** Semi-hardcoded, with GFF files (hierachical data, similar to XML in spirit) describing the setup. The xoreos-tools repository has a tool for converting GFF files into XML for easy reading.
* Dialogues
** DLG files, similar to NWN
** Some extensions, like camera setup
** Dialogues are displayed very different than NWN
** KotOR2 has script extensions
*** Passing parameters to scripts
*** Call several scripts, combine with AND/OR for branching
* Animations
** Should be similar to NWN
** No player character shown
*** Needs character creator menus
*** Loading of character files in class Creature
* Minigames
** Swoop racing
** Pazaak
** Hardcoded, mostly removed from usual game logic

=== Jade Empire ===
* Menus
** Apparently very similar to KotOR's menus
* Minigames
** Flyer, top-down shoot-em-up thing
** Hardcoded, mostly removed from usual game logic
* Player character
** Needs research
* Sound
** Uses an ASCII variant of the [http://wiki.multimedia.cx/index.php?title=XACT XACT formats]
*** Cues probably not as complex as FMOD/Wwise
*** Effects need extension of the Sound system, maybe
** Xbox version might use the binary format?
*** Sound banks could be handles as archives and indexed in the ResourceManager?
** [https://github.com/FNA-XNA/FNA/tree/master/src/Audio FNA] has an implementation of XACT. Probably quite useful to look at that

=== NWN2 ===
* Menus
** Implemented using XML
** See [[#Broken NWN2 XML|Broken NWN2 XML]]
* Animations (Granny)
** [https://github.com/SkywingvL/nwn2dev-public nwn2-dev] contains some code working with Granny data
*** Call into the original Granny DLL to convert between binary and ASCII Granny data, though
** [https://github.com/berenm/xoreos-tools/tree/granny berenm started some Granny RE]
* Facial animations (FaceFX)
* Trees (SpeedTree)
* Proper evaluation of creature model parts (equipped items)
* Player character
** Reading of PC files in creature

=== Sonic Chronicles ===
* Allow using the contents from an extracted NDS file?
* Menus
** GUI files that are GFF
** Actions in a state machine in GDA files?
* Music/Sound
** Music is apparently similar to MIDI, or to a tracker format?
** Sounds and instruments for music are in a sound_data.sadl archive
* Animations
** Bone animations, best implemented with shaders, blocked by the graphics subsystem rewrite
* Player character(s)
** Needs research

=== The Witcher ===
* Menus
** Apparently build using Lua
** System/Scripts/ has gui*.luc files
* Animations
** Needs research
* Player character, Geralt
** Needs research

=== Dragon Age: Origins / Dragon Age 2 ===
* Menus
** [https://en.wikipedia.org/wiki/Scaleform_GFx Scaleform GFx]
** [http://social.bioware.com/wiki/datoolset/index.php/UI_Tutorial_%28draft%29 UI Tutorial] on the Dragon Age toolset wiki
** Flash-based!
** A good starting point for a reimplementation might be [https://en.wikipedia.org/wiki/Gameswf Gameswf].
** [https://en.wikipedia.org/wiki/Gnash Gnash], [https://en.wikipedia.org/wiki/Lightspark Lightspark], [https://en.wikipedia.org/wiki/Swfdec Swfdec]
** [http://www.nowrap.de/flasm.html Flasm] can disassemble/assemble ActionScript, [http://www.nowrap.de/flare.html Flare] can decompile it
* Animations
** Bone animations, best implemented with shaders, blocked by the graphics subsystem rewrite

Pathfinding

2017-04-26T16:04:03Z

Supermanu: /* Simple Stupid Funnel Algorithm */ technical details

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [#A.2A_algorithm first image]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

== Simple Stupid Funnel Algorithm ==
The 'SSFA' is relatively straighforward technicaly. The main difficulty is about creature's size. In order to take it into account, the 'POC' computes tangents between the circles around vertices.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-26T14:19:25Z

Supermanu: /* External libraries */

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [#A.2A_algorithm first image]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convince me at first sight.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-26T11:06:19Z

Supermanu: Add External libraries

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [#A.2A_algorithm first image]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

=== External libraries ===
Several geometric functions are needed to make everything work (intersections between different polygons, distances,…) though most of them in the 'POC' are home-made/based on google results, some use Boost.geometry (at least one) for simplicity sake. I guess, we should use this library as most as possible from a maintenance, efficiency and performance perspective. There is also [http://www.cgal.org/ CGAL] that seems complete though it didn't convinced me at first sight.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-19T16:11:13Z

Supermanu: Restructure

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

= How pathfinding works? =

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

== A* algorithm ==

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

== Simple Stupid Funnel Algorithm ==

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

== Other steps ==

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

= Show me the code! =

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

== Walkmesh data format ==

=== KotOR ===

=== Nwn ===

== A* Algorithm ==

Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

=== Graph structure ===
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

=== Open list ===
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

=== Estimation and heuristic function ===
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [#A.2A_algorithm first image]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

= References =

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-19T15:45:01Z

Supermanu: /* Estimation and heuristic function */

= Pathfinding =

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

== How pathfinding works? ==

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

=== A* algorithm ===

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

=== Simple Stupid Funnel Algorithm ===

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

=== Other steps ===

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

== Show me the code! ==

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

=== Walkmesh data format ===

==== KotOR ====

==== Nwn ====

=== A* Algorithm ===
Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

==== Graph structure ====
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

==== Open list ====
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

==== Estimation and heuristic function ====
The total estimation when ''A*'' tries to find the best next node, is given by the sum of two functions. The current cost function that gives the current length of the path. and the heuristic function that estimates the length to the end. In the ''POC'', the former is measured by the path going through the middle of each edge it crosses (as seen in the [#A.2A_algorithm first image]). This could obviously changed, one can take the center of a face/triangle (incenter, centroid, …) for instance. The more naive heuristic function is simply the direct length to the endpoint. Again this could be improved in some specific cases, as the ''walkmesh'' is built from several parts (tiles, rooms,…), one can directly run ''A*'' on those by considering them as one big face. It could be a real improvement in maze like areas.

== References ==

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-17T20:08:48Z

Supermanu: /* Open list */

= Pathfinding =

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

== How pathfinding works? ==

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

=== A* algorithm ===

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

=== Simple Stupid Funnel Algorithm ===

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

=== Other steps ===

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

== Show me the code! ==

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

=== Walkmesh data format ===

==== KotOR ====

==== Nwn ====

=== A* Algorithm ===
Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

==== Graph structure ====
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

==== Open list ====
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with big/complex walkmesh.

== References ==

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-17T19:56:49Z

Supermanu: /* Open list */ Link to boost.heap

= Pathfinding =

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

== How pathfinding works? ==

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

=== A* algorithm ===

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

=== Simple Stupid Funnel Algorithm ===

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

=== Other steps ===

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

== Show me the code! ==

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

=== Walkmesh data format ===

==== KotOR ====

==== Nwn ====

=== A* Algorithm ===
Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

==== Graph structure ====
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

==== Open list ====
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as [http://www.boost.org/doc/libs/1_63_0/doc/html/heap.html boost.heap] which is, imho, more complete. Though performance drops might only appear with ''big'' walkmesh.

== References ==

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-17T19:55:33Z

Supermanu: /* Open list */

= Pathfinding =

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

== How pathfinding works? ==

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

=== A* algorithm ===

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

=== Simple Stupid Funnel Algorithm ===

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

=== Other steps ===

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

== Show me the code! ==

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

=== Walkmesh data format ===

==== KotOR ====

==== Nwn ====

=== A* Algorithm ===
Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

==== Graph structure ====
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

==== Open list ====
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]]. The ''POC'' uses a <code>std::vector</code> which is sorted whenever a node is added. This is obviously not the fastest way to do it. <code>std::priority_queue</code> could be used as well as <code>boost.heap</code> which is, imho, more complete. Though performance drops might only appear with ''big'' walkmesh.

== References ==

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-17T19:44:05Z

Supermanu: /* A* Algorithm */

= Pathfinding =

This is a collection of thoughts, documentations, mumbling, and explanation of the work done about pathfinding. Any ideas or comments are more than welcome.

Up to now, only KotOR and nwn have been investigated. Any "findings" might not apply to other games.

== How pathfinding works? ==

The engine seems to use a [https://en.wikipedia.org/wiki/Navigation_mesh navigation mesh] or ''walkmesh'' as the underlying data structure. It is simply a polygon mesh where each face has a ''walk property'' to state if an agent/creature can walk on this particular face and what kind of material the face is (metal, carpet, grass,…).

=== A* algorithm ===

[[File:walkmesh_path_search.png|center|thumb|none|550x344px|Walkmesh in KotOR. The green faces are unwalkable. The pink adjacent faces represent a path between two points.]]

The first step in pathfinding, is to find a series of adjacent faces among the navigation mesh that constitutes a path between two points. Ideally, the path is the shortest one but it highly depends on the quality of the ''walkmesh'' and the kind of algorithm used. As we want to reuse what is already there – the ''walkmesh'' – our only leverage will be the algorithm part though some pre-processing steps on the ''walkmesh'' might be needed as explained later.

There are several algorithms that tries to achieve that goal. [https://en.wikipedia.org/wiki/A*_search_algorithm ''A*''] and all its variants is a widely used algorithm in games and real-time applications, it is both accurate and fast though it won’t necessarily give the best path but one of the bests. Basically, it will start from an endpoint of the path and try to go around, on another face, and estimates if it is closer to the other side of the path. The main area one can improve about the algorithm’s performance is on the way it thinks how closer it moves to the end. The function that gives this estimation is called the ''heuristic'' and will be discussed later.

=== Simple Stupid Funnel Algorithm ===

[[File:SSFA.png|center|thumb|none|525x328px|Another pathfinding search in KotOR using A* and the Simple Stupid Funnel Algorithm.]]

Once we have a series of adjacent faces, comes the second step: to have a nice line our creature can follow. Again, there are several algorithms able to address that kind of issue, though I will focus on the [http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html Simple Stupid Funnel Algorithm](''SSFA'') taken from Mikko Mononen blogpost and author of the Recast and Detour toolset. The idea behind ''SSFA'', is like pulling two strings from the start to each border of the faces path. The algorithm goes from vertex to vertex that belongs to the border and must make the funnel formed by the two strings narrower at each iteration and lie inside the faces path. Otherwise, it has to pull the strings from a previous vertex. As an image is worth a thousand words:

[[File:SSFA_explained.png|center|thumb|297x327px]]

On the above image, A-B-C-D steps narrow the funnel. In the E step, the red string cannot move since it would be outside the path. In the F step, the two strings are crossing so it has to restart from a previous vertex in the next iteration ''i.e.'' the G step.

One thing that ''SSFA'' doesn’t directly take into account is creature’s size. In deed, it gives us a path that sticks to the border. To deal with it, one trick[1] is to consider a circle around each vertex that cannot be crossed by the funnel.

[[File:SSFA_size.png|center|277x261px]]
[[File:pathfinding_smooth.png|center|503x320px]]

=== Other steps ===

While we can have <s>a beautiful</s> an acceptable path with ''A*'' and ''SSFA'' algorithms, the job is far from being done. First, the ''walkmesh'' doesn’t take into account all static objects like crates or seats. Somehow, some of those static objects are included in the walkmesh and some don’t (screw you bioware!). An idea to deal with that, would be to add those static objects to the walkmesh directly as a pre-processing step or simply consider them as dynamic objects.

Anyway, pathfinding also have to handle dynamic objects ''i.e.'' the ones that can move, be destroyed or spontaneously appear. Contrary to the previous steps, this needs to be done along the path a creature is taking. I guess it should be independent from ''A*'' and ''SSFA'' and done by scanning with rays or something else what’s in front of the creature in real-time.

== Show me the code! ==

A first proof of concept has been made in this [https://github.com/Supermanu/xoreos/tree/pathfinding branch]. It is an awful code with lot of dead code and stuff nobody should ever see. It only works (''A*'' and ''SSFA'') with KotOr but has some code for nwn. Also, it needs [http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/index.html Boost.Geometry] to run. Let’s try to explain the code in details and the choices made.

=== Walkmesh data format ===

==== KotOR ====

==== Nwn ====

=== A* Algorithm ===
Though each game comes with it's own walkmesh dataformat, at the end we need an underlying structure that will store the walkmesh. In the ''POC'', the walkmesh is stored in 5 <code>std::vector</code>:
* A vector of float which contains the vertices,
* A vector of <code>UINT32</code> for each face of the walkmesh. It stores the related vertices and thus is three times the total number of faces (which are triangles).
* A vector of <code>UINT32</code> for adjacent faces. It stores for each side of a face, the adjacent face. <code>UINT32_MAX</code> is used when there is no adjacent face.
* A vector of <code>UINT32</code> for face property. It stores the kind of material the face is.
* A vector of [https://en.wikipedia.org/wiki/Bounding_volume AABB] trees. Each leaf of an AABB tree embeds a face. This allows to make fast face search based on coordinate.

==== Graph structure ====
''A*'' is graph based algorithm with nodes and edges. Different choices can be made on what nodes and edges are. Vertices and faces can be taken as nodes as well as a side of a face, the edges being what connects them. For simplicity sake, in the ''POC'', face has been taken as node and face adjacency as edge. Other choices could lead to better or worst performances as regards of the length of the path and time spent.

==== Open list ====
''A* uses a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand'' [[https://en.wikipedia.org/wiki/A*_search_algorithm#Description Wikipedia]].

== References ==

[1] '''Efficient Triangulation-Based Pathfinding''', ''Douglas Demyen and Michael Buro''.

Pathfinding

2017-04-16T18:59:06Z

Supermanu: Initial content for pathfinding page: How pathfinding works?

File:Pathfinding smooth.png

2017-04-16T18:34:36Z

Supermanu: Walkmesh in KotOR and path search with A*, SSFA with creature's size.

Walkmesh in KotOR and path search with A*, SSFA with creature's size.

File:SSFA size.png

2017-04-16T18:31:53Z

Supermanu: Illustration of the Simple Stupid Funnel Algorithm taking account creature's size.

Illustration of the Simple Stupid Funnel Algorithm taking account creature's size.

File:SSFA explained.png

2017-04-16T18:10:03Z

Supermanu: Different steps of Simple Stupid Funnel Algorithm from Mikko Mononen's blog post http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html

Different steps of Simple Stupid Funnel Algorithm from Mikko Mononen's blog post http://digestingduck.blogspot.be/2010/03/simple-stupid-funnel-algorithm.html

File:SSFA.png

2017-04-16T18:03:25Z

Supermanu: Walkmesh and path search with the Simple Stupid Funnel Algorithm.

Walkmesh and path search with the Simple Stupid Funnel Algorithm.

File:Walkmesh path search.png

2017-04-15T19:52:55Z

Supermanu: Walkmesh in KotOR and an A* path search.

Walkmesh in KotOR and an A* path search.

Neverwinter Nights/Research

2016-06-23T18:56:23Z

Supermanu: How walkmesh may work

== Lighting ==

original NWN for linux uses:

<pre>
glLightModelfv(pname = GL_LIGHT_MODEL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_AMBIENT, params = {0.160784, 0.160784, 0.160784, 1})
glLightfv(light = GL_LIGHT1, pname = GL_DIFFUSE, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_SPECULAR, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_POSITION, params = {4000, 4500, 7000, 1})
glLightfv(light = GL_LIGHT1, pname = GL_QUADRATIC_ATTENUATION, params = &4.5e-10)
glLightfv(light = GL_LIGHT2, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT2, pname = GL_DIFFUSE, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_SPECULAR, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_POSITION, params = {16.43526, 8.189793, 2.922178, 1})
glLightfv(light = GL_LIGHT2, pname = GL_QUADRATIC_ATTENUATION, params = &0.02543954)
</pre>

or

<pre>
glLightfv(light = GL_LIGHT1, pname = GL_AMBIENT, params = {0.160784, 0.160784, 0.160784, 1})
glLightfv(light = GL_LIGHT1, pname = GL_DIFFUSE, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_SPECULAR, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_POSITION, params = {4000, 4500, 7000, 1})
glLightfv(light = GL_LIGHT1, pname = GL_QUADRATIC_ATTENUATION, params = &4.5e-10)
glLightfv(light = GL_LIGHT2, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT2, pname = GL_DIFFUSE, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_SPECULAR, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_POSITION, params = {16.43526, 8.189793, 2.922178, 1})
glLightfv(light = GL_LIGHT2, pname = GL_QUADRATIC_ATTENUATION, params = &0.02543954)
glLightfv(light = GL_LIGHT3, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT3, pname = GL_DIFFUSE, params = {1.3, 1.92, 1.82, 1})
glLightfv(light = GL_LIGHT3, pname = GL_SPECULAR, params = {1.3, 1.92, 1.82, 1})
glLightfv(light = GL_LIGHT3, pname = GL_POSITION, params = {14.99999, 4.999998, 5, 1})
glLightfv(light = GL_LIGHT3, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
glLightfv(light = GL_LIGHT4, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT4, pname = GL_DIFFUSE, params = {2, 0.5, 0.2, 1})
glLightfv(light = GL_LIGHT4, pname = GL_SPECULAR, params = {2, 0.5, 0.2, 1})
glLightfv(light = GL_LIGHT4, pname = GL_POSITION, params = {14.02705, 2.55035, 4, 1})
glLightfv(light = GL_LIGHT4, pname = GL_QUADRATIC_ATTENUATION, params = &0.18)
glLightfv(light = GL_LIGHT5, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT5, pname = GL_DIFFUSE, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT5, pname = GL_SPECULAR, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT5, pname = GL_POSITION, params = {14.9855, 1.83074, 1.62787, 1})
glLightfv(light = GL_LIGHT5, pname = GL_QUADRATIC_ATTENUATION, params = &0.09183674)
glLightfv(light = GL_LIGHT6, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT6, pname = GL_DIFFUSE, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT6, pname = GL_SPECULAR, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT6, pname = GL_POSITION, params = {5, 15, 5, 1})
glLightfv(light = GL_LIGHT6, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
glLightfv(light = GL_LIGHT7, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT7, pname = GL_DIFFUSE, params = {0.196573, 0.1474298, 0.05897192, 1})
glLightfv(light = GL_LIGHT7, pname = GL_SPECULAR, params = {0.196573, 0.1474298, 0.05897192, 1})
glLightfv(light = GL_LIGHT7, pname = GL_POSITION, params = {5, 5, 5, 1})
glLightfv(light = GL_LIGHT7, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
</pre>

for light0 the following is used:

<pre>
glLightModelfv(pname = GL_LIGHT_MODEL_AMBIENT, params = {1, 1, 1, 1})
glLightfv(light = GL_LIGHT0, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT0, pname = GL_DIFFUSE, params = {1, 1, 1, 1})
glLightfv(light = GL_LIGHT0, pname = GL_POSITION, params = {0, 0, 742.4, 1})
</pre>

== Walkmesh ==

The way nwn determines where a character/creature can or cannot walk seems to involve two different parts: a mesh and AABB[https://en.wikipedia.org/wiki/Bounding_volume] for collision detection. Those two parts can be found in a tile model ".mdl" and is associated ".wok" file (an ASCII file). The data in the model and in the wok seems to be almost redundant: slightly different at the mesh level.

=== Mesh ===

The mesh can be found in both the mdl and the wok. In the mdl, it can be found as a normal mesh in the node that contains both AABB and mesh flags. Each face of the mesh have a smooth property that can be related to a specific material. The material properties is in the "surfacemat.2da" file where the index is the smooth value. The 2da file contains two columns with boolean values, "Walk" and "WalkCheck", that should surely indicates where one can walk or not.

=== AABB ===

Similarly to the mesh, AABBs can be found in the model in the same node and directly in the wok file. AABBs come as a binary tree, each leaf from that tree is related to a specific face from the walkmesh and surrounds it. It is the ''part_number_leaf_face''[https://github.com/xoreos/xoreos-docs/blob/master/templates/NWN1MDL.bt#L601] property that relates to the face.

=== Difference between mdl and wok ===

The shape of the mesh in the mdl and the wok are the same though the number of vertices differs. In deed, in the mdl one can find more or less three times the number of vertices regarding the wok. In fact, almost each face in the mdl has its own vertices, only a few share some vertices.

About AABB, it seems they are the same in both files.

=== How it could work ===

There are two cases. First, when the user want to know where he can/cannot go by moving the cursor. In this case, the intersection between the ray coming from the camera and the AABB tree will give a AABB leaf node, its related face and thus if it is walkable or not. Second, when a creature want to move, it needs to know if it can, what sound should be played and the vertical position of the creature. The intersection in the XY plan of the creature's bounding box and the AABB tree should give similarly as the former case if the creature can be moved. For the vertical position, one hypothesis would be that it is given from the intersection between the XY position of the creature and the related face from the AABB leaf node.

Neverwinter Nights/Research

2016-03-16T10:57:04Z

Supermanu: /* AABB */ Add info about leaf face property

Neverwinter Nights/Research

2016-03-09T15:47:02Z

Supermanu: Add info about walkmesh

== Lighting ==

original NWN for linux uses:

<pre>
glLightModelfv(pname = GL_LIGHT_MODEL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_AMBIENT, params = {0.160784, 0.160784, 0.160784, 1})
glLightfv(light = GL_LIGHT1, pname = GL_DIFFUSE, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_SPECULAR, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_POSITION, params = {4000, 4500, 7000, 1})
glLightfv(light = GL_LIGHT1, pname = GL_QUADRATIC_ATTENUATION, params = &4.5e-10)
glLightfv(light = GL_LIGHT2, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT2, pname = GL_DIFFUSE, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_SPECULAR, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_POSITION, params = {16.43526, 8.189793, 2.922178, 1})
glLightfv(light = GL_LIGHT2, pname = GL_QUADRATIC_ATTENUATION, params = &0.02543954)
</pre>

or

<pre>
glLightfv(light = GL_LIGHT1, pname = GL_AMBIENT, params = {0.160784, 0.160784, 0.160784, 1})
glLightfv(light = GL_LIGHT1, pname = GL_DIFFUSE, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_SPECULAR, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT1, pname = GL_POSITION, params = {4000, 4500, 7000, 1})
glLightfv(light = GL_LIGHT1, pname = GL_QUADRATIC_ATTENUATION, params = &4.5e-10)
glLightfv(light = GL_LIGHT2, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT2, pname = GL_DIFFUSE, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_SPECULAR, params = {1.75, 1.5, 1, 1})
glLightfv(light = GL_LIGHT2, pname = GL_POSITION, params = {16.43526, 8.189793, 2.922178, 1})
glLightfv(light = GL_LIGHT2, pname = GL_QUADRATIC_ATTENUATION, params = &0.02543954)
glLightfv(light = GL_LIGHT3, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT3, pname = GL_DIFFUSE, params = {1.3, 1.92, 1.82, 1})
glLightfv(light = GL_LIGHT3, pname = GL_SPECULAR, params = {1.3, 1.92, 1.82, 1})
glLightfv(light = GL_LIGHT3, pname = GL_POSITION, params = {14.99999, 4.999998, 5, 1})
glLightfv(light = GL_LIGHT3, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
glLightfv(light = GL_LIGHT4, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT4, pname = GL_DIFFUSE, params = {2, 0.5, 0.2, 1})
glLightfv(light = GL_LIGHT4, pname = GL_SPECULAR, params = {2, 0.5, 0.2, 1})
glLightfv(light = GL_LIGHT4, pname = GL_POSITION, params = {14.02705, 2.55035, 4, 1})
glLightfv(light = GL_LIGHT4, pname = GL_QUADRATIC_ATTENUATION, params = &0.18)
glLightfv(light = GL_LIGHT5, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT5, pname = GL_DIFFUSE, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT5, pname = GL_SPECULAR, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT5, pname = GL_POSITION, params = {14.9855, 1.83074, 1.62787, 1})
glLightfv(light = GL_LIGHT5, pname = GL_QUADRATIC_ATTENUATION, params = &0.09183674)
glLightfv(light = GL_LIGHT6, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT6, pname = GL_DIFFUSE, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT6, pname = GL_SPECULAR, params = {0.1847787, 0.1847787, 0.09828652, 1})
glLightfv(light = GL_LIGHT6, pname = GL_POSITION, params = {5, 15, 5, 1})
glLightfv(light = GL_LIGHT6, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
glLightfv(light = GL_LIGHT7, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT7, pname = GL_DIFFUSE, params = {0.196573, 0.1474298, 0.05897192, 1})
glLightfv(light = GL_LIGHT7, pname = GL_SPECULAR, params = {0.196573, 0.1474298, 0.05897192, 1})
glLightfv(light = GL_LIGHT7, pname = GL_POSITION, params = {5, 5, 5, 1})
glLightfv(light = GL_LIGHT7, pname = GL_QUADRATIC_ATTENUATION, params = &0.045)
</pre>

for light0 the following is used:

<pre>
glLightModelfv(pname = GL_LIGHT_MODEL_AMBIENT, params = {1, 1, 1, 1})
glLightfv(light = GL_LIGHT0, pname = GL_AMBIENT, params = {0, 0, 0, 1})
glLightfv(light = GL_LIGHT0, pname = GL_DIFFUSE, params = {1, 1, 1, 1})
glLightfv(light = GL_LIGHT0, pname = GL_POSITION, params = {0, 0, 742.4, 1})
</pre>

== Walkmesh ==

The way nwn determines where a character/creature can or cannot walk seems to involve two different parts: a mesh and AABB[https://en.wikipedia.org/wiki/Bounding_volume] for collision detection. Those two parts can be found in a tile model ".mdl" and is associated ".wok" file (an ASCII file). The data in the model and in the wok seems to be almost redundant: slightly different at the mesh level.

=== Mesh ===

The mesh can be found in both the mdl and the wok. In the mdl, it can be found as a normal mesh in the node that contains both AABB and mesh flags. Each face of the mesh have a smooth property that can be related to a specific material. The material properties is in the "surfacemat.2da" file where the index is the smooth value. The 2da file contains two columns with boolean values, "Walk" and "WalkCheck", that should surely indicates where one can walk or not.

=== AABB ===

Similarly to the mesh, AABB can be found in the model in the same node and directly in the wok file.

=== Difference between mdl and wok ===

The shape of the mesh in the mdl and the wok are the same though the number of vertices differs. In deed, in the mdl one can find more or less three times the number of vertices regarding the wok. In fact, almost each face in the mdl has its own vertices, only a few share some vertices.

About AABB, it seems they are the same in both files.