AMP-G2 Tables

Posts relating to the Pathfinder project
mSparks
Advanced Member
Posts: 996
Joined: Fri Jan 03, 2003 2:54 pm
Location: North West UK
Contact:

Postby mSparks » Fri Feb 20, 2004 3:39 pm

AMP-G2 Tables: Area-based Multiple Path-Generation 2 tables.
AMP-G2 tables are a new feature to be included in 1.7final and in the various incarnations of the TBM_AI software developer kit. They are algorithmic data built from standard node files. They serve as a mid layer between node files (point to point neighbour infomation) and path tables (shortest route infomation from one point to another, navigating environment changes).
The primary aim is to allow the AI to make (high speed/low tick count)inteligent choices when deciding to go from one place to another, but they also allow more intelligent choice of primary goal navigation and facilitate team based movement and spacing. All this has been mentioned before, but this 'article' discusses in more detail what is involved and the implications when dealing with pathfinding infomation.

To appreciate the difference between an area and a node, what they represent needs to be considered.

A node: Is a single point in space, links between them join these points in space, 'node density' determins how far apart these nodes are placed (and in no particular order). Nodes in open spaces may have many links, where tight and confined spaces will have nodes with less links.

An Area: is a group of several nodes and represent portions of space rather than a single point. They have volume and linking properties and can for instance represent rooms, corridors along with having sub areas (such as a room within a building).

AMP-G2 tables are areas built automatically, containing the node areas, linkage, volume etc. Some of the generated infomation can be viewed using the latest incarnation of the pathfinder project.

AMP-G2 has several implications.
Firstly, goals no longer need to be chosen on a node by node basis, and instead can be chosen directly from areas (and since there are considerably less areas to handle, learning curves are steeper, and data processing is faster).
A major benifit comes when finding the closest node to a point in space (such as when starting a point to point route). Previously, the only way to reliably find this node was by searching through the entire list to find the closest visible node. Whilst different techinques and optimisations for this have been tried, there is not much defference to starting at the first node and cycling through untill a match is found. Whilst the effect of this has been minimised by ensuring minimal calls to the findnode, it still represents a significant portion of time when it is called.
Enter AMP-G2 tables. By ordering the node ID's into the areas, the area can be easily found based on volume infomation and then the best node found by searching this areas nodes (and possibly sub areas). on average this gives a speed increase of aproximately 10-15x, considerable improving the performance of this function.

More details to follow.
© Mark 'mSparks' Parker 2010
<pubkey>AJXzWKeV59HaoUkmrCwP9f+kMr8aOIM
jMKy7ACsaRDCE/XuF0orj/jActtfWDMKjg/CixI7JP0Z6lbS99dc
86fxDIQOmfIU8BNYKPmlPA/uY3ZpT9/4iQY0XwKad5eJhDFW
cZ2Z4VUWJzlbuoX/QV4ihTVkr9JnyJb+fN9AOqXH9AQAB</pubkey>

User avatar
RiviEr
Advanced Member
Posts: 49
Joined: Mon Aug 18, 2003 6:55 pm
Location: Norway, Oslo
Contact:

Postby RiviEr » Fri Feb 20, 2004 9:55 pm

AMP-G2 Table holds quite much information to the learning process right? dark area, bad area, cover area etc?

-RiviEr

mSparks
Advanced Member
Posts: 996
Joined: Fri Jan 03, 2003 2:54 pm
Location: North West UK
Contact:

Postby mSparks » Sun Feb 22, 2004 3:53 pm

AMP-G2 Table holds quite much information to the learning process right? dark area, bad area, cover area etc?

well.. not exactly, the're more part of an optimisation process of building environmental data for the AI to gather this infomation without having todo masses of calculations on the fly. Game environments exist in much the same manner as real world environments; walls/obstructions, interactive points (e.g. doors/buttons) hieghts and lights, visability points etc. As players, we have to physically learn (by playing) what implications and impacts each of these various features have on gameplay. origonally the AI handled infomation on a much more simplistic approach, building infomation databases for handling various tasks, mainly for picking one route to a point over another (standard route tables only handle shortest route infomation, such as its shorter to go through a building rather than around it). An AMP-G2 table physically divides groups of nodes into areas, and the areas linkage, rather than points in space (such as the center of a corridor, and its volume). which is what makes the whole concept of 'sub areas' possible. (e.g. a room, with sub areas of next to walls, center, and space in front of the door) with minimal 'on the fly' calculation.
© Mark 'mSparks' Parker 2010

<pubkey>AJXzWKeV59HaoUkmrCwP9f+kMr8aOIM
jMKy7ACsaRDCE/XuF0orj/jActtfWDMKjg/CixI7JP0Z6lbS99dc
86fxDIQOmfIU8BNYKPmlPA/uY3ZpT9/4iQY0XwKad5eJhDFW
cZ2Z4VUWJzlbuoX/QV4ihTVkr9JnyJb+fN9AOqXH9AQAB</pubkey>

User avatar
RiviEr
Advanced Member
Posts: 49
Joined: Mon Aug 18, 2003 6:55 pm
Location: Norway, Oslo
Contact:

Postby RiviEr » Tue Feb 24, 2004 11:41 am

I need to try this :D

-RiviEr


Return to “Pathfinder”

Who is online

Users browsing this forum: No registered users and 1 guest