## Recommended Posts

I am currently attempting to make a navigation mesh for our 2D top down game, which is a multiplayer game using Node.js as the server communication. At the moment, I have implemented A* over an obstacle hardnessmap, which is awfully slow and laggy at times when we test our game on Heroku. I have been trying to find an algorithm to automatically generate the navmesh after map creation, instead of me having to do this manually. I am currently attempting to use Delaunay's Triangulation Divide and Conquer algorithm, but I am running into some issues. I have already asked a question on StackOverflow and am not getting many suggestions and help from it, so I figured I would come here. Is there another algorithm that might be better to use for the navmesh generation in comparison to Deluanay's Triangulation? My current implementation seems extremely buggy during the merge step and I cannot find the error. I have checked over the code countless times, comparing it to the description of the algorithm from http://www.geom.uiuc.edu/~samuelp/del_project.html

My current code is this:

class MapNode
{
constructor(x, y)
{
this.position = new Vector(x, y);
this.neighbors = [];
}

distance(n)
{
return this.position.distance(n.position);
}

inNeighbor(n)
{
for (let i = 0; i < this.neighbors.length; i++)
{
if (this.neighbors[i] === n)
return true;
}

return false;
}

{
this.neighbors = this.neighbors.filter((node) => node != n);
this.neighbors.push(n);
}

{
let self = this;
arr.forEach((n) => self.neighbors.push(n));
}

removeNeighbor(n)
{
this.neighbors = this.neighbors.filter((neighbor) => neighbor != n);
}
}

class Triangle
{
constructor(p1, p2, p3)
{
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;

this.neighbors = [];
}

{
this.neighbors.push(n);
}
}

function genSubMat(matrix, ignoreCol)
{
let r = [];
for (let i = 0; i < matrix.length - 1; i++)
{
r.push([]);
for (let j = 0; j < matrix[0].length; j++)
{
if (j != ignoreCol)
r[i].push(matrix[i + 1][j]);
}
}

return r;
}

function determinantSqMat(matrix)
{
if (matrix.length != matrix[0].length) return false;

if (matrix.length === 2) return matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1];

let det = 0;
for (let i = 0; i < matrix.length; i++)
{
let r = genSubMat(matrix, i);
let tmp = matrix[0][i] * determinantSqMat(r);
if (i % 2 == 0)
det += tmp;
else
det -= tmp;
}

return -det;
}

// if d is in the circle formed by points a, b, and c, return > 0
// d is on circle, return 0
// d is outside of circle, return < 0
function inCircle(a, b, c, d)
{
let arr = [a, b, c, d];
let mat = [
[],
[],
[],
[]
];

for (let i = 0; i < arr.length; i++)
{
mat[i][0] = 1;
mat[i][1] = arr[i].position.x;
mat[i][2] = arr[i].position.y;
mat[i][3] = arr[i].position.x * arr[i].position.x + arr[i].position.y * arr[i].position.y;
}
return determinantSqMat(mat);
}

function walkable(from, to, hardnessMap)
{
let diff = new Vector(to.x - from.x, to.y - from.y);
if (Math.abs(diff.x) > Math.abs(diff.y)) diff.scale(Math.abs(1 / diff.x));
else diff.scale(Math.abs(1 / diff.y));
let current = new Vector(from.x + diff.x, from.y + diff.y);
while (Math.round(current.x) != to.x || Math.round(current.y) != to.y)
{
if (hardnessMap[Math.floor(current.y)][Math.floor(current.x)] === 1)
return false;
current.x += diff.x;
current.y += diff.y;
}

return true;
}

function getLowest(nodes)
{
let lowest = nodes[0];
for (let i = 1; i < nodes.length; i++)
{
if (nodes[i].position.y < lowest.position.y)
lowest = nodes[i];
}

return lowest;
}

// returns the angle between 2 vectors, if cw is true, then return clockwise angle between,
// else return the ccw angle between. b is the "hinge" point
function angleBetween(a, b, c, cw)
{
let ba = new Vector(a.position.x - b.position.x, a.position.y - b.position.y);
let bc = new Vector(c.position.x - b.position.x, c.position.y - b.position.y);
let v0 = new Vector(0, 1);

let angleBA = v0.angleBetween(ba) * 180 / Math.PI;
if (angleBA < 0) angleBA += 360;
let angleBC = v0.angleBetween(bc) * 180 / Math.PI;
if (angleBC < 0) angleBC += 360;

let smallest = Math.min(angleBA, angleBC);
let largest = Math.max(angleBA, angleBC);

let angle = largest - smallest;

return (cw) ? angle : 360 - angle;
}

function sortSmallestAngle(a, b, list, cw)
{
list.sort((m, n) =>
{
let vab = new Vector(a.position.x - b.position.x, a.position.y - b.position.y);
let vmb = new Vector(m.position.x - b.position.x, m.position.y - b.position.y);
let vnb = new Vector(n.position.x - b.position.x, n.position.y - b.position.y);

if (cw)
return vab.angleBetween(vmb, cw) - vab.angleBetween(vnb, cw);
else
return vab.angleBetween(vnb, cw) - vab.angleBetween(vmb, cw);
});
}

// a is in list, b is in the other list
function getPotential(a, b, list, cw)
{
sortSmallestAngle(b, a, list, cw);
for (let i = 0; i < list.length - 1; i++)
{
let angle = angleBetween(b, a, list[i], cw);
if (angle > 180) return false;
else if (inCircle(a, b, list[i], list[i + 1]) <= 0)
return list[i];
else
{
a.removeNeighbor(list[i]);
list[i].removeNeighbor(a);
}
}

let potential = list[list.length - 1];
if (potential)
{
let angle = angleBetween(a, b, potential, cw);
if (angle > 180) return false;
return potential;
}
return false;
}

function merge(leftNodes, rightNodes, leftBase, rightBase, hardnessMap)
{

let newLeft = leftNodes.filter((n) => n != leftBase);
let newRight = rightNodes.filter((n) => n != rightBase);

let potentialLeft = getPotential(leftBase, rightBase, newLeft, false);
let potentialRight = getPotential(rightBase, leftBase, newRight, true);

if (!potentialLeft && !potentialRight) return;
else if (potentialLeft && !potentialRight)
merge(newLeft, newRight, potentialLeft, rightBase, hardnessMap);
else if (potentialRight && !potentialLeft)
merge(newLeft, newRight, leftBase, potentialRight, hardnessMap);
else
{
if (inCircle(leftBase, rightBase, potentialLeft, potentialRight) <= 0)
merge(newLeft, newRight, potentialLeft, rightBase, hardnessMap);
if (inCircle(leftBase, rightBase, potentialRight, potentialLeft) <= 0)
merge(newLeft, newRight, leftBase, potentialRight, hardnessMap);
}
}

// divide and conquer algorithm
function delaunay(nodes, hardnessMap)
{
if (nodes.length <= 3)
{
for (let i = 0; i < nodes.length; i++)
for (let j = 0; j < nodes.length; j++)
if (i != j)

return nodes;
}
else
{
nodes.sort((a, b) =>
{
let tmp = a.position.x - b.position.x;
if (tmp === 0) return b.position.y - a.position.y;
return tmp;
});

let l = nodes.length;

let leftNodes;
let rightNodes;

if (l === 4)
{
leftNodes = delaunay(nodes.slice(0, 3), hardnessMap);
rightNodes = delaunay(nodes.slice(3, 4), hardnessMap);
}
else
{
leftNodes = delaunay(nodes.slice(0, Math.floor(nodes.length / 2)), hardnessMap);
rightNodes = delaunay(nodes.slice(Math.floor(nodes.length / 2), nodes.length), hardnessMap);
}
let leftBase = getLowest(leftNodes);
let rightBase = getLowest(rightNodes);

merge(leftNodes, rightNodes, leftBase, rightBase, hardnessMap);

console.log("=============================MergeComplete================================");
return nodes;
}
}

## Create an account

Register a new account

• 10
• 16
• 9
• 13
• 41
• ### Similar Content

• Overview
Welcome to the 2D UFO game guide using the Orx Portable Game Engine. My aim for this tutorial is to take you through all the steps to build a UFO game from scratch.
The aim of our game is to allow the player to control a UFO by applying physical forces to move it around. The player must collect pickups to increase their score to win.
I should openly acknowledge that this series is cheekily inspired by the 2D UFO tutorial written for Unity.
It makes an excellent comparison of the approaches between Orx and Unity. It is also a perfect way to highlight one of the major parts that makes Orx unique among other game engines, its Data Driven Configuration System.
You'll get very familiar with this system very soon. It's at the very heart of just about every game written using Orx.
If you are very new to game development, don't worry. We'll take it nice and slow and try to explain everything in very simple terms. The only knowledge you will need is some simple C++.
I'd like say a huge thank you to FullyBugged for providing the graphics for this series of articles.

What are we making?
Visit the video below to see the look and gameplay of the final game:
Getting Orx
The latest up to date version of Orx can be cloned from github and set up with:
git clone https://github.com/orx/orx.git Once cloning has completed, the setup script in the root of the files will start automatically for you. This script creates an $ORX environment variable for your system. The variable will point to the code subfolder where you cloned Orx. Why? I'll get to the in a moment, but it'll make your life easier. The setup script also creates several projects for various IDEs and operating system: Visual Studio, Codelite, Code::Blocks, and gmake. You can pick one of these projects to build the Orx library. Building the Orx Library While the Orx headers are provided, you need to compile the Orx library so that your own games can link to it. Because the setup script has already created a suitable a project for you (using premake), you can simply open one for your chosen OS/IDE and compile the Orx library yourself. There are three configurations to compile: Debug, Profile and Release. You will need to compile all three. For more details on compiling the Orx lbrary at: http://orx-project.org/wiki/en/tutorials/cloning_orx_from_github at the Orx learning wiki. The$ORX Environment Variable
I promised I would explain what this is for. Once you have compiled all three orx library files, you will find them in the code/lib/dynamic folder:
orx.dll orxd.dll orxp.dll Also, link libraries will be available in the same folder:
orx.lib orxd.lib orxp.lib When it comes time to create our own game project, we would normally be forced to copy these library files and includes into every project.
A better way is to have our projects point to the libraries and includes located at the folder that the $ORX environment variable points to (for example: C:\Dev\orx\code). This means that your projects will always know where to find the Orx library. And should you ever clone and re-compile a new version of Orx, your game projects can make immediate use of the newer version. Setting up a 2D UFO Project Now the you have the Orx libraries cloned and compiled, you will need a blank project for your game. Supported options are: Visual Studio, CodeLite, Code::Blocks, XCode or gmake, depending on your operating system. Once you have a game project, you can use it to work through the steps in this tutorial. Orx provides a very nice system for auto creating game projects for you. In the root of the Orx repo, you will find either the init.bat (for Windows) or init.sh (Mac/Linux) command. Create a project for our 2D game from the command line in the Orx folder and running: init c:\temp\ufo or init.sh ~/ufo Orx will create a project for each IDE supported by your OS at the specified location. You can copy this folder anywhere, and your project will always compile and link due to the$ORX environment variable. It knows where the libraries and includes are for Orx.
Open your project using your favourite IDE from within the ufo/build folder.
When the blank template loads, there are two main folders to note in your solution:
config src Firstly, the src folder contains a single source file, ufo.cpp. This is where we will add the c++ code for the game. The config folder contains configuration files for our game.
What is config?
Orx is a data driven 2D game engine. Many of the elements in your game, like objects, spawners, music etc, do not need to be defined in code. They can be defined (or configured) using config files.
You can make a range of complex multi-part objects with special behaviours and effects in Orx, and bring them into your game with a single line of code. You'll see this in the following chapters of this guide.
There are three ufo config files in the config folder but for this guide, only one will actually be used in our game. This is:
ufo.ini All our game configuration will be done there.
Over in the Orx library repo folder under orx/code/bin, there are two other config files:
CreationTemplate.ini SettingsTemplate.ini These are example configs and they list all the properties and values that are available to you. We will mainly concentrate on referring to the CreationTemplate.ini, which is for objects, sounds, etc. It's good idea to include these two files into your project for easy reference.
Alternatively you can view these online at https://github.com/orx/orx/blob/master/code/bin/CreationTemplate.ini and here: https://github.com/orx/orx/blob/master/code/bin/SettingsTemplate.ini

The code template
Now to take a look at the basic ufo.cpp and see what is contained there.
The first function is the Init() function.
This function will execute when the game starts up. Here you can create objects have been defined in the config, or perform other set up tasks like handlers. We'll do both of these soon.
The Run() function is executed every main clock cycle. This is a good place to continually perform a task. Though there are better alternatives for this, and we will cover those later. This is mainly used to check for the quit key.
The Exit() function is where memory is cleaned up when your game quits. Orx cleans up nicely after itself. We won't use this function as part of this guide.
The Bootstrap() function is an optional function to use. This is used to tell Orx where to find the first config file for use in our game (ufo.ini). There is another way to do this, but for now, we'll use this function to inform Orx of the config.
Then of course, the main() function. We do not need to use this function in this guide.
Now that we have everything we need to get start, you should be able to compile successfully. Run the program and an Orx logo will appear slowly rotating.

Great. So now you have everything you need to start building the UFO game.
If you experience an issue compiling, check the troubleshooting article for Orx projects    for help.

Setting up the game assets
Our game will have a background, a UFO which the player will control, and some pickups that the player can collect.
The UFO will be controlled by the player using the cursor keys.
First you'll need the assets to make the game. You can download the file  assets-for-orx-ufo-game.zip which contains:
The background file (background.png😞

The UFO and Pickup sprite images (ufo.png and pickup.png😞

And a pickup sound effect (pickup.ogg😞
pickup.ogg
Copy the .png files into your data/texture folder
Copy the .ogg file into your data/sound folder.
Now these files can be accessed by your project and included in the game.

Setting up the Playfield
We will start by setting up the background object. This is done using config.
Open the ufo.ini config file in your editor and add the following:

[BackgroundGraphic] Texture = background.png Pivot = center
The BackgroundGraphic defined here is called a Graphic Section. It has two properties defined. The first is Texture which has been set as background.png.
The Orx library knows where to find this image, due to the properties set in the Resource section:

[Resource] Texture = ../../data/texture
So any texture files that are required (just like in our BackgroundGraphic section) will be located in the ../../data/texture folder.
The second parameter is Pivot. A pivot is the handle (or sometimes “hotspot” in other frameworks). This is set to be center. The position is 0,0 by default, just like the camera. The effect is to ensure the background sits in the center of our game window.
There are other values available for Pivot. To see the list of values, open the CreationTemplate.ini file in your editor. Scroll to the GraphicTemplate section and find Pivot in the list. There you can see all the possible values that could be used.
top left is also a typical value.
We need to define an object that will make use of this graphic. This will be the actual entity that is used in the game:

[BackgroundObject] Graphic = BackgroundGraphic Position = (0, 0, 0)
The Graphic property is the section BackgroundGraphic that we defined earlier. Our object will use that graphic.
The second property is the Position. In our world, this object will be created at (0, 0, 0). In Orx, the coordinates are (x, y, z). It may seem strange that Orx, being a 2D game engine has a Z axis. Actually Orx is 2.5D. It respects the Z axis for objects, and can use this for layering above or below other objects in the game.
To make the object appear in our game, we will add a line of code in our source file to create it.
In the Init() function of ufo.cpp, remove the default line:
orxObject_CreateFromConfig("Object"); and replace it with:
orxObject_CreateFromConfig("BackgroundObject"); Compile and run.
The old spinning logo is now replaced with a nice tiled background object.

Next, the ufo object is required. This is what the player will control. This will be covered in Part 2.
• By xDanix
Hi guys, so im developing a game using GMS2, following shaun spalding tutorials from youtube, my problem is that he explains only the basics on the mechanics, and since i have almost 0 knowledge in code, i cannot derail far from what he writes.. the main issue that i have now is developing the character animation; i want to make a jump, something like: impulse, ascending, descending, landing and also some smooth transition between ascencion and descent. now, in the way he wrote the code i get as follows:
// animation
if (!place_meeting(x,y+1,oWall))
{
sprite_index = sPlayerA;
image_speed = 0;
if (sign(vsp) > 0) image_index = 1; else image_index = 0;
}
oWall is my collision object, sPlayerA is my jump sprite with two frames on it.
that gives me a basic and solid jump, but i feel like its too static.... Any ideas on how to write something to get a nice smooth jump with more than just two frames? i'm aiming at four or five frames total.
thanks in advance, here's a screenshot of the work in progress:

• By Aggrojag
Hello!
I'm working on a game that is a narrative driven dark comedy with some small aspects of platforming and puzzle solving. The project is rather small as well. It touches on topics such as suicide, mental illness, family, corruption, free-will, and redemption.
This project is exercise in polish, this means some experimentation will be needed along with some reworking of assets as they're provided.
This will be a revshare model.
First, I'm looking for a 2D sprite artist, not pixelated, that can compliment the style of the attached images, and be similar to the temporary character.
We are looking to bring on a SFX designer at this time. Full list of required SFX will be available upon request, as well as a build with all elements related to sound implemented in some form (many SFXs pulled from the web for now). Will likely require some field recording, and some pretty strange SFX for when things get weird. I imagine a good portion of these will be quite fun to create.
Lastly, I'm looking for a male voice actor, English should be your primary language. There will be at minimum two characters that will need to be brought to life through vocals. The first voice is similar to Marvin from Hitchhiker's Guide to the Galaxy. A reference for the second voice would be a mix of Ren (Ren & Stimpy), and Android 21 (DragonBallFighterZ). Due to formatting, I'm not including YouTube links in the post, sorry.

WIP Scene with our custom shaders attached (platforms are lazily placed, as this was an asset test):

A scene with dynamic lighting and temp character:

If you made it to the bottom, thank you, and I look forward to hearing from you.

• like this?

const D3DXMATRIX robertx = D3DXMATRIX(1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1);

• Hello,
I want to get into coding again by programming a 2D platformer to get started, but i don't know if i should use Java or C# with the unity engine.
I am pretty fit with Java, but with c# i have to start from scratch. What do you recommend and why?