Search for a path through NavMesh in ActionScript - CrossBridge port Recast Navigation

In this article I will talk about the experience of porting C ++ code to ActionScript using the FlasCC compiler and show how I managed to port a fairly large amount of useful code that solves the problem of finding a path. At the end there will be a demo and a link to the repository with the code. In the meantime, a few words about how it all began.

I am working on an indieproject. This is a top-view shooter (similar to Crimsonland). I am writing a project on AS3. The game space is continuous (not in cells) and is based on the Nape physics engine. Impassable areas (walls) are described by a set of convex polygons. The problem arises of navigating agents (monsters) on such a map.

What are some ideas for solving this problem?
')
1. The space can be divided into cells and reduced to the task of finding a path on a checkered field. For this, there are already ready-made solutions on Flash. But I did not like this option because it forces the agent to always move from a certain cell to a neighboring one. This decision also does not take into account the size of the agent, which may be different.

2. You can build a cross graph. If the agent cannot reach the target in a straight line, then the algorithm finds the targets closest to the agent, a couple of nodes of the graph and builds a route along the graph between them. I implemented this approach in my project as a temporary one. It was set up like this: in the level editor, nodes were set (waypoints), without specifying any links. During the loading of the level, the system determined the direct passability between all possible pairs of nodes and thus defined the connections between them. This decision suited me for a while, but soon some shortcomings began to annoy me:
- The size of the agents is still not taken into account. It would be great if on the basis of patency for agents of different sizes it was possible to build situations in the game.
- Nodes have to be set in the editor manually. It is unpleasant that in general this topic has to constantly return. And the quality of the routes depends on how well the nodes are placed.
- Routes are not optimal. Often a situation began to arise when the agent first goes “from the target” to the nearest node and only starts following from it, since other nodes in the straight cross was not.
- Agents do not take into account the existence of each other. When moving a crowd of monsters, the linearity of their movement is very noticeable and does not look realistic.

3. Another approach is the navigation mesh. The idea is this: the passable area of ​​the map is covered by a set of convex polygons adjoining each other. Inside each polygon, the agent can move freely. This is a very good solution for my case, I began to look for what tools exist on the Flash. It turned out that in general there is nothing. But there is a C ++. The toolbox is called Recast Navigation - this is a pretty serious thing and it has absolutely everything you need. For the sake of fairness, I’ll note that there is a Rekast demo ported through Alchemy on Github, but this is only a demo that cannot be reused.

And then I realized that I needed it. I began to think how to transfer it to AS3. Moving a little aside, I’m saying that before using the Nape physics engine, I tried to use Box2D, which is available in Flash in two versions: rewritten to AS3 and ported using Alchemy. The version rewritten on AS3 had the disadvantage that every change, whether it was a corrected error or a new functionality, required the manual transfer of the corresponding code to the Flash version of the engine. At some point he was simply abandoned. But I liked the port through Alchemy in principle. In addition to just a set of functions that repeat the API of the original engine, the author added an AS3 set of wrapper classes for the corresponding classes and structures in C ++. Thus, the API in the Flash version hid from the developer the need to follow the transfer of pointers, operating simply with wrapper classes.

I decided to port everything through CrossBridge (formerly Alchemy). CrossBridge is a Cygwin based environment with its own gcc compiler. The compiler is called FlasCC and it outputs ActionScript bytecode at the output. The general work flow is this: Each method in C ++ is associated with a method in AS3, which repeats the prototype of the C ++ function as accurately as possible. A set of such functions is compiled using FlasCC in swc. Then this swc connects to the project, in which another swc is created with the final API (with documentation) hiding pointers, memory allocations, etc. from the AS3 developer.

Like the original code, I decided to make this port open. All code is here: github.com/Rokannon/Crossbridge-Recast-Navigation
The repository with the original code in C ++ added as a submodule.

A small demo of what happened, you can see here:
work.rokannon.com/navmesh_demo
In the panel on the right, you need to select the source mesh, which describes the level geometry. Next, you need to scroll the panel down, click "Build" and wait a little while NavMesh is built. In the panel on the left there are two tools that demonstrate the capabilities of the toolset: finding a path and navigating a crowd of agents.

Transferred not all functions, but very many. So the code can already be used. Subscribe to the repository to follow the updates.

At this official part is over. Thanks for attention. If someone has any questions - ask.

Well, then, for those who are interested in the subtleties of implementation, I described the techniques that I used when porting C ++ code to AS3.

Simplest example

#include <AS3\AS3.h> // ,     AS3. float testFunc(x:float, y:float) { return x + y; } void _testFunc() __attribute__((used, annotate("as3sig:public function internal_testFunc(x:Number, y:Number):Number"), annotate("as3package:ctest"))); void _testFunc() { float x; AS3_GetScalarFromVar(x, x); //    -,  - AS3. float y; AS3_GetScalarFromVar(y, y); AS3_Return(x + y); } 

Running CrossBridge can compile this code:

 /cygdrive/c/Crossbridge_1.0.1/sdk/usr/bin/g++ "main.cpp" -emit-swc=ctest -o "out.swc" 

As a result, the resulting swc will have the function internal_testFunc (x: Number, y: Number): Number that performs the same as testFunc in C ++. Absolutely all functions are ported to this pattern. The prefix internal_ is chosen specifically because completely hide this method from the final swc will not work.

Structures

This class is used as a base for the class wrapper structures:

 package ctest { use namespace c_internal; public class CBase { c_internal var ptr:int; public function alloc():Boolean { return false; } public function free():void { CModule.free(ptr); } } } 

What does it make sense to pay attention here? A wrapper class stores the address of the structure or class that wraps it. There are no pointers in AS3. Instead, they simply use int. The variable ptr should be available everywhere except for the final API, so it is hidden by the special custom namespace c_internal.

Consider the following structure in C ++:

 struct MyStruct { int x, int y }; 

Such a structure as a wrapper class will correspond to:

 package ctest { use namespace c_internal; public class MyStruct extends CBase { c_internal static var SIZE:int = 0; c_internal static const OFFSET_X:int = offset(4); c_internal static const OFFSET_Y:int = offset(4); private static function offset(size:int):int { return (SIZE += size) - size; } public function get x():int { return CModule.read32(ptr + OFFSET_X); } public function set x(value:int):void { CModule.write32(ptr + OFFSET_X, value); } public function get y():int { return CModule.read32(ptr + OFFSET_Y); } public function set y(value:int):void { CModule.write32(ptr + OFFSET_Y, value); } public override function alloc():Boolean { ptr = CModule.alloc(SIZE); return ptr != 0; } } } 

Here, a small trix allows you to conveniently calculate the indents of all the fields and get the size of the structure as a bonus. But there is one pitfall associated with memory alignment : Roughly speaking, if the data does not fit completely into one word (4 bytes), then their indentation should be a multiple of 4 bytes. For example, the structure:

 struct ExampleStruct { char x, char y, int z } 

It is located by bytes like this: XY 0 0 ZZZZ . And sizeof(ExampleStruct) is 8, not 6 bytes.

Functions with pointers in arguments

 #include <AS3\AS3.h> void addNum(MyStruct* s, int n) { s->x += n; s->y += n; } void _addNum() __attribute__((used, annotate("as3sig:public function internal_addNum(s_ptr:int, n:int):void"), annotate("as3package:ctest"))); void _testFunc() { MyStruct* s; AS3_GetScalarFromVar(s, s_ptr); int n; AS3_GetScalarFromVar(n, n); addNum(s, n); } 

To hide the need for a pointer from the developer, the final API will have the following function:

 package ctest { use namespace c_internal; public function addNum(s:MyStruct, n:int):void { internal_addNum(s.ptr, n); } } 

Pointer functions

 #include <AS3\AS3.h> MyStruct* sum(MyStruct* s1, MyStruct* s2) { s1->x += s2->x; s1->y += s2->y; return s1; } void _sum() __attribute__((used, annotate("as3sig:public function internal_sum(s1_ptr:int, s2_ptr:int):int"), annotate("as3package:ctest"))); void _testFunc() { MyStruct* s1; AS3_GetScalarFromVar(s1, s1_ptr); MyStruct* s2; AS3_GetScalarFromVar(s2, s2_ptr); AS3_Return(sum(s1, s2)); } 

Since the wrapper does not store any data about the structure / class being wrapped except the address, it is convenient to add it as an optional argument to the API method:

 package ctest { use namespace c_internal; public function sum(s1:MyStruct, s2:MyStruct, resultMyStruct:MyStruct = null):MyStruct { if (resultMyStruct == null) { resultMyStruct = new MyStruct(); } resultMyStruct.ptr = internal(s1.ptr, s2.ptr); return resultMyStruct; } } 

A similar technique is used to refer to the elements of an array.