Project Perfect Mod Forums
:: Home :: Get Hosted :: PPM FAQ :: Forum FAQ :: Privacy Policy :: Search :: Memberlist :: Usergroups :: Register :: Profile :: Log in to check your private messages :: Log in ::


The time now is Sun May 26, 2024 12:08 pm
All times are UTC + 0
Openage Development News: March 2024
Moderators: Global Moderators
Post new topic   Reply to topic Page 1 of 1 [1 Post] Mark the topic unread ::  View previous topic :: View next topic
Author Message
Banshee
Supreme Banshee


Also Known As: banshee_revora (Steam)
Joined: 15 Aug 2002
Location: Brazil

PostPosted: Thu Apr 04, 2024 5:42 pm    Post subject:  Openage Development News: March 2024
Subject description: Improving the pathfinder algorithms that will help as a compass to advance to the next development stages!
Reply with quote  Mark this post and the followings unread

Greetings, commander! We bring news from Openage. For those who are not acquainted with it, Openage is a free cross-platform Real Time Strategy game engine that provides the mechanics of Age of Empires, replicating its look and feel, making it more moddable, and allowing multiplayer games with more than eight players. Here are the official words about it:

Quote:
Hello, everyone, and welcome to another round of openage updates. If you enjoyed the pathfinding explanations from our last devlog, you can probably start getting excited because this month's
post will be all about even more fun pathfinding features. However, we hope that those of you who are not avid pathfinding aficionados can have some fun, too. So, let's get to it.

Line of Sight Optimization
In last month's update, we showed off the flow fields that are created by our new pathfinder implementation. Essentially, the idea behind flow fields is that instead of computing a single path from start A to target B, we generate a vector field for the whole grid where every cell gets assigned a vector that points towards the next cheapest cell for reaching B. As a result, units anywhere on the grid can follow (or flow) along these vectors to eventually arrive at the target (see below).



target cell == (7,7); origin is left corner

  • yellow == less expensive
  • purple == more expensive
  • black == impassible

In this example, you can see that the flow field vectors only support eight directions. A side effect of this is that paths become diamond-shaped, i.e., they have turns of at least 45 degrees. While this may not be as noticeable when you are just looking at the static flow field, it can be very annoying when observing units in motion. When controlling units, most players would expect them to go in a straight line if there are no obstacles between the start and target (and not take a detour into a castle's line of fire).
For this reason, we have to do some low-level optimization that smoothes out short-distance paths in these situations.

One of these optimizations is a so-called line-of-sight pass. In this preliminary step, we flag every cell that can be reached from the target in a straight line with a "line-of-sight" flag. Units in these cells can then be pathed directly towards the target in a straight line without having to use the vector field. You can see the results of doing such a line-of-sight pass in the image below.



target cell == (1,4); origin is left corner

  • white == line-of-sight flag
  • light grey == blocked flag
  • dark grey == passable, but no line-of-sight
  • black == impassible

Impassable cells or cells with more than minimum cost are considered line-of-sight blockers and are assigned a separate "blocked" flag. The same goes for cells that are only partially in line-of-sight, e.g., cells that are on the line between the blocker cells' outer corners and the edge of the grid. The cells marked as "blocked" form the boundaries of line-of-sight vision cones that span across the grid.

For cells with a "line-of-sight" flag, we can skip calculating flow field vectors as they are no longer necessary for finding a path.

Travelling with Portals
One advantage of flow fields is that the generated field may be reused for multiple path requests to the same target, e.g., group movement of units. While reusing the fields can save computation time in this context, the complexity of flow field calculations makes the initial cost of building the flow field much higher than for other pathfinding methods. On larger grids, this can make individual path requests incredibly slow.

To solve this problem, we can utilize a simple trick: We split the pathfinding grid into smaller sectors, e.g., with size 16x16, and search for a high-level path through these sectors first. Afterward, we only calculate flow fields for the sectors that are visited and ignore the rest of the grid.

To accomplish this, sectors are connected via so-called portals. Portals are created on the pathable edges between two sectors. Additionally, portals in the same sector are connected to each other if they are mutually reachable. The result is a mesh of portal nodes that can be searched with a high-level pathfinder. For the high-level pathfinder, we can use a node-based approach instead of flow fields, e.g., the A* algorithm, to search the mesh. Finding the high-level path should usually be pretty fast, as it only depends on the number of portals on the grid.


  • white == passable
  • grey == portal tiles
  • black == impassible

What's next?
The only major step left in the pathfinder integration is to include it in the actual game simulation, i.e., building it into map/terrain generation. This should be easier than the implementation of the pathfinder itself, but it will take some effort to get it right. If pathfinding becomes too tedious, we might switch things up and work on something else for a short while. In any case, you will find out what we decided to do in next month's update!

Questions?
Any more questions? Let us know and discuss those ideas by visiting our subreddit /r/openage!

As always, if you want to reach us directly in the dev chatroom:

  • Matrix: #sfttech:matrix.org


If you are curious about Openage, visit the Official Website, Forums, and YouTube Video Channel to obtain further information about it. And that's all regarding Openage for now. Stay tuned at PPM for more news about Openage!


Key Words: #News #OpenAge 

_________________


Mods, Mods Support, Public Researchs, Map Archives, Tutorials, A Friendly Community and much more. Check it out now!

Back to top
View user's profile Send private message Visit poster's website Skype Account
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [1 Post] Mark the topic unread ::  View previous topic :: View next topic
 
Share on TwitterShare on FacebookShare on Google+Share on DiggShare on RedditShare on PInterestShare on Del.icio.usShare on Stumble Upon
Quick Reply
Username:


If you are visually impaired or cannot otherwise answer the challenges below please contact the Administrator for help.


Write only two of the following words separated by a sharp: Brotherhood, unity, peace! 

 
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © phpBB Group

[ Time: 0.1826s ][ Queries: 11 (0.0067s) ][ Debug on ]