Pathfinding, MR and Telemetry

SUHAS

New Member
GSOC/TSOC 2020
This is the weekly forum post thread for my TSoC 2020 project! Forum posts done here will be a quick summary of progress during the week, and a meeting summary. Much of the actual work, and implementation details will be mentioned in the blog mentioned below.

This project aims at improving pathfinding in Terasology. It plans to implement a precached path system in the form of road networks to be used by NPCS for navigation because running the entire pathfinding algorithm every time is too time-intensive. Later, improvements to the way cities are laid out will be made with varying heights for the building generators. Finally, (something that is of a completely different area) for the logistics aspects, log enrichment to suit the needs for kibana querying will be made. Kibana dashboards will be set up that will allow developers to get a better view of the data in the backend.
 

SUHAS

New Member
GSOC/TSOC 2020
Week 1
Things done
  • Organised cards better into their topics
  • Added a temporal order to the tasks and seperated into chunks
  • Went through various existing tests for Pathfinding (to assist in implementing PF myself)
  • Gained a better understanding of all the tasks in chunk 1, and researched most of the aspects that might be needed.
To be done this week

  • Implement a Slope Facet like Roughness Facet which stores slopes at different points in the terrain.

Things I'm concerned about.

  • How to implement a grid system.
  • Easier testing of paths either using WorldViewer or Pathdebugger (JFrame based)
  • Time complexity of the algorithm is O(n3). Might have to condense many nodes into one
  • How to cache paths. Found a cachebuilder somewhere but not sure yet. Pathcache in NavgraphChunk
Importatant references
https://gamedev.stackexchange.com/questions/89824/how-can-i-compute-a-steepness-value-for-height-map-cells
StaticCities/terrain/BuildableTerrainFacet.java
isbuildable only checks if height is 3 blocks above sea level

building material based on biome it is a part of?
SimpleBiomeProvider

HeightmapSurfaceHeightProvider

Currently in DC, it only measures the mean deviation, and City is modelled whenever the mean SD lies in a particular range. (SiteFacetProvider.java)
Confused about
  • what regions are
  • infinitesurface?
  • how static cities currently chooses regions.
  • trying to get a grip of numbers and scales in which Terrain works. Like gridsize=4 ?
  • pathfinder gives an arraylist of walkable blocks


Some final thoughts
Maybe have a way of storing all the discussions we have on discord in a nicer way?
Along the way try to finalize a log format and try to fix the ingress and SSL issue.
Wondering if skaldarnars github demo already happened, because I could really use some help in using the intricacies of git and learning good practices in development.
 

SUHAS

New Member
GSOC/TSOC 2020
Week 1

Meeting minutes.
--------------------------------------------------------------------------------------------------------------------------------
Theta* makes pathfinding and roads play nice with each other anyways, so don't need to worry about that.
Discussed possibilities of using 2D sight algorithms.
Discussed using KD Trees for grid systems for Cities.
Got a better idea of the entire pathfinding aspect by dividing it into 3 aspects
  1. pathfinding(in the wild)
  2. laying roads
  3. making pathfinding and roads play nice
Discussed the pros and cons of using just pathfinding vs implementing a new structure like KD Tree.
 

SUHAS

New Member
GSOC/TSOC 2020
Week 1
This week was really slow because I had some school work to complete and assignments to submit. It also took me a while to get my workspace set up with intellij. Maybe it takes time to get the wheels rolling, so the weeks to come will definitely be much more productive with most of my commitments going away.

This week was filled with fruitful discussion with casals and others over the possible ways of taking the main aspects of the project forward, with discussions regarding KD trees, sight algorithms. Some other aspects that I was confused about have been cleared, like how storing just the nodes would not be sufficient and information regarding the edges would also need to be stored.

I implemented a slope facet that determined the slope at different points in the terrain. It used finite differencing to approximate the derivative with respect to x and with respect to z and the vectors were then added. However, I later found out another implementation which calculated the normal at a position in the terrain and then calculated the slope (Thanks to skaldarnar). Which method will suit better can only be ascertained with testing.

Further I read through and understood most of the working of the minion move to and move along path behaviours (linked to pathfinding), and tried implementing the same in Metal Renegades. Currently, only a simple move_to behaviour node is present in the NPCs behaviour tree causing them to only have a primitive , go in a straight line mechanism. This results in the NPCs to be stuck behind walls helplessly trying to make it across. This will be fixed in the coming weeks.

Things blocking me right now.
How to get the slope facet information integrated into pathfinding.
  1. inject the slopefacet provider into pathfinding and create an A*withSlopeCosts class in pathfinding that uses this information.
  2. inject and use the slope facet provider within DC and then pass the cost function (with slope and distance information) into Pathfinding API (General pathfinder's computepath() method) which returns a path.
Still need a quicker method of testing paths.
To be done next week.
Complete implementation of A* with slope costs.
Write tests for it
 

SUHAS

New Member
GSOC/TSOC 2020
Week 2
Highlights:

  • This week was mostly filled with gaining a deeper understanding of the implementation details of Path-finding that is implemented.
  • After finding out that even a simple form of path finding was not working, I changed focus into trying to figure out what was wrong and trying to fix it.
  • I was able to implement a simple form of slope inclusion into the path costs (without facets) and opened a PR.
  • I was able to draft up an optimisation to the current path-finding that would allow us to know whether the target node would even be reachable before even trying to start the pathfinding algorithm. (PR will be finalised after discussion with casals)
  • I was able to narrow down the issue with empty paths being returned to the fact that walkable blocks were not being connected or initialised with their neighbours. I believe that this is happening because the NavGraphSystem is not keeping track of the added blocks (which are added in DC. Example, while filling the floor beneath houses). The entities then request a path from a point that supposedly seems like a point in the air (for the NavgraphSystem atleast).Hence, no path is returned.(Simply because there are no connected walkableblocks to the block in the air.) I opened an issue with my findings. (Hopefully resolve this soon).
Blockers:
  • Integrating SteepnessFacet information into pathfinding.
  • Taking a lot of time to understand the nooks and crannies of the implementation of pathfinding.
  • A way for testing paths.
I was of the impression that MetalRenegades did have some sort of primitive path-finding system incorporated into MR. However, only a direct-line travel exists with some jumping (and a lot of getting stuck in weird places). That explains the gooeys jumping against the walls. So I decided that fixing this was the most important because only afterwards would I be able to test the amount of time it takes for paths and things like that. The issue happening currently is probably related to the NavGraphSystem unable to detect the changes that happen through DC placing the blocks. (For example, while filling )

With respect to integrating slopes into pathfinding. I was unable to actually integrate the steepnessfacets into pathfinding itself because the regions that were defined within the module is different from the actual regions and I wasnt able to figure out a way to plug it in. Hence I implemented a much simpler version that would approximately give the right value.

This week, I also came across this idea where we could mark all the reachable nodes with a particular id. Thus, only if both the start and end nodes had the same id, would the search even start thus saving us a lot of time. However, this has an added complexity when dealing with NavGraphChanged events as the whole region would have to be again filled with ids. For example, if a region was seperated due to blocks being placed, then the different regions would have to be given seperate ids. Again, if a block was removed, or a connection between regions was made, both the regions must now have the same price. These would require utility functions again which would run a simple flood fill on the regions. (But there might be some interesting edge cases).
 

SUHAS

New Member
GSOC/TSOC 2020
Week 2
Meeting Minutes
  • Meeting time pushed back an hr.
  • Discussion on maybe using chunks and thus accessing facet information from there.
  • Discussions on making the pathfinding module more extensible, giving the caller more control over how the costs are set, possibly using callbacks
  • Possible work on logistics aspects side by side. Figuring out how to get logs that are sent to logstash to appear in kibana would be the first steps.
 
Top