Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 07 Jul 2011
Offline Last Active Jan 22 2015 02:04 PM

Topics I've Started

a few questions regarding navigation meshes

29 November 2013 - 02:37 PM

I am working on a small 2D game and my goal is to make the AI as the most proficient feature of the game. The space in which in the my characters will move within is continuous just like in 3D or RTS games. I studied some books/surfed the internet and I decided that implementing navigational meshes to represent search spaces seems to be the most appropriate technique.


But, I am new at this and I have few questions for which I have not been able to find satisfactory answers.


(i) Is it necessary for the navmesh polygons to be convex?


(ii) If I have a point(x,y) in my 2D world and I have the navigational meshes specified for the level, how do I know on which mesh polygon I am currently standing on(localization)?


My guess: If I have 'n' number of polygons in my level and each of them are specified with their own set of vertices, then this becomes a O(n) problem in the worst case. I would have to check each polygon for the existence of that point within it.


(iii) How do I generate a graph data structure from the navmesh for the A* pathfinding algorithm to use?


My guess: From my understanding, this becomes a O(n²) problem in the worst case, provided that we have 'n' number of polygons in the level and each polygon has its own set of vertices. For each polygon, I would have to look at every other polygon in the worst case and find if anyone of the pairs shares at least one vertex with each other. If they do, then they become neighboring nodes.


(iv) For heuristic calculations(euclidean distance) and conversion from graph node to game position, which point in a polygon should I use?


My guess: The centroid of a convex navmesh polygon seems to be the most appropriate choice. If we have 'n' number of vertices for a polygon, then from my understanding, calculating the point of centroid seems to become a O(n) problem.


That is all the questions I have right now. Kindly, please also give me some tips on to how should I organize the data of navmesh polygons into a meaningful data structure?


Any help will be greatly appreciated,

Thank you. smile.png

Need advice on pathfinding implementation

16 November 2013 - 10:17 AM

I have to write a simple 3D game in which I would like to implement an agent that can navigate through a map that has walls and simple static obstacles...


Now, I have studied the A* algorithm and was able to successfully write my own algorithm in c++... The algorithm runs on a rectangular grid with all the grids of being the same size... and can calculate optimal paths using euclidean distance as the heuristic...


Well, I have searched the internet and some game programming books and saw that just writing an A* algorithm is not enough, I need to have search space representation which in my case is a rectangular grid, translation of agents and 3D world knowledge between the algorithm and the game...


I was looking into some search space representation techniques and one of the most popular being navmesh and waypoints... I have read that pathfinding using waypoints in not recommended anymore and navmesh is the most popular among current AI developers...


Now, my issue is that I have never worked or programmed nav meshes before and this is the first time I am writing a game that has an AI component or NPCs...


How should I approach this? should I start by how to automatically generate navigation meshes for a level? or adjusting my algorithm to support navigation meshes?


I would gladly appreciate any advice...

Library linking problem with SDL 2.0

17 August 2013 - 02:21 PM

I have used CodeBlocks with MinGW to use opengl with SDL 1.2 and I was able to link libraries that are required for MinGW to work with SDL 1.2, these static libraries are mingw32.lib, SDLmain.lib and SDL.lib. However, I just got SDL 2.0 and I having trouble linking libraries with my SDL 2.0 project.


I did the same procedure, I went to Project->Build Options->Linker Settings and added three libraries that are required for SDL 2.0 (I extracted the library files to the MinGW lib folder and the include files to the MinGW include folder, the static lib files are in .a extension and written as libSDLmain.a instead of SDLmain.lib) and add three files under link libraries with names of "libmingw32" "libSDL2main" "libSDL2". In the search directories tab I added the path to the MinGW lib folder where I placed my SDL static library files...


I wrote the code and checked carefully for deprecated and changed function names that are in SDL 2.0...


When I compiled the code, I am getting these errors


obj\Debug\app.o||In function `ZN3app9onExecuteEv':|
D:\Programming\SDL OpenGL\app.cpp|19|undefined reference to `SDL_PollEvent'|
obj\Debug\appOnInitialize.o||In function `ZN3app12onInitializeEv':|
D:\Programming\SDL OpenGL\appOnInitialize.cpp|5|undefined reference to `SDL_Init'|
D:\Programming\SDL OpenGL\appOnInitialize.cpp|24|undefined reference to `SDL_CreateWindow'|
D:\Programming\SDL OpenGL\appOnInitialize.cpp|27|undefined reference to `SDL_GL_CreateContext'|
obj\Debug\appOnRender.o||In function `ZN3app8onRenderEv':|
D:\Programming\SDL OpenGL\appOnRender.cpp|15|undefined reference to `SDL_GL_SwapWindow'|
C:\Program Files\CodeBlocks\MinGW\lib\libmingw32.a(main.o):main.c:(.text.startup+0xa7)||undefined reference to `WinMain@16'|
||=== Build finished: 6 errors, 0 warnings (0 minutes, 0 seconds) ===|


I did a lot of google searches but I am not able to configure how to sove this...

I am a noob with configuring compilers and linking and building libraries in C++, can someone please guide me how can I solve this in my CodeBlocks IDE?


Thank you

File input, get stream pointer's position

25 September 2012 - 07:57 AM

Hi, I'm writing a program where I have to manipulate the stream pointer in an input file. I wrote a testing program, I wanted to test if I get the right pointer position in a file where I have written few strings in a single line.

The contents of the file are "hello world foo(int) a=b".
The code is
#include <iostream>
using namespace std;
#include <fstream>
int main()
	ifstream Infile;
	char c;
	if (Infile.is_open())
		Infile.seekg(0, ios::beg);
		while (!Infile.eof())
			cout << Infile.tellg() << ' ';
	return 0;
The output of the program is
0 2 4 6 8 10 12 14 16 18 20 22 24 26

However, should'nt it be
0 1 2 3 4 5 6 7 8 9 10 11 12 13 and so on....

Because I am reading one character at a time and from what I know, the get(char) function also reads whitespaces and endlines...

I don't understand why the position pointer is being incremented by two and not one!!? However if manipulate the pointer using seekg() func, it returns the character at that position but If i use tellg() and just read input, then it increments the pointer by two...
Any clues?

Camera and Viewing Transformations

18 August 2012 - 09:44 PM

First of all, I am aware that there is no such entity called camera in OpenGL. The eye is located at the origin looking down the negative z-axis with the up vector being the positive y-axis (please correct me if I am wrong here or anywhere).

So here's the deal, I am trying to make a class that will handle the view of the scene using keyboard input. Just like in an aircraft, there is thrust which causes the camera to move forward(if we are sitting in a cockpit). Let us say, I am using W and S keys to control the thrust of this hypothetical camera and A and D keys to control my heading(the direction at which I am looking) and Up and Down keys to control the Pitch and Left and Right to control Roll.

If you have ever played Descent, there are actually ten ways to control the ship. Thrust forward, backward.. slide left, right, slide up and down, Pitch up and down, and roll left and right.

This is what I am trying to do here. By using basic opengl transformation functions I want to build my own camera class that I can control the view the scene very easily and how I want to view it.

Here is the code so far that I was able to do:
#include <SDL.h>
#include <GLEW\glew.h>
#include <math.h>
#include "Misc.h"
const GLfloat INCREMENT_HEADING = 0.1f;
const GLfloat INCREMENT_PITCH = 0.1f;
const GLfloat INCREMENT_ROLL = 0.1f;
const GLfloat INCREMENT_FORWARD = 1.0f;
// From Right to Left, in Bits, the keys are
// right left down up d a s w
class EyeCam
    GLfloat Angle_Heading;
    GLfloat Angle_Pitch;
    GLfloat Angle_Roll;
    Uint8 KeyState;
    GLfloat eyeX, eyeY, eyeZ;
    EyeCam(GLfloat eyeX, GLfloat eyeY, GLfloat eyeZ, GLfloat aimX, GLfloat aimY, GLfloat aimZ);
    void onEvent(SDL_Event* event);
    void update();

#include "EyeCam.h"
#include <iostream>
EyeCam::EyeCam(GLfloat eyeX, GLfloat eyeY, GLfloat eyeZ, GLfloat aimX, GLfloat aimY, GLfloat aimZ)
    this->eyeX = eyeX;
    this->eyeY = eyeY;
    this->eyeZ = eyeZ;
    Angle_Heading = Misc::toDegrees(atan2f((eyeX - aimX), (eyeZ - aimZ)));
    GLfloat base = sqrt(pow(eyeZ-aimZ, 2) + pow(eyeX - aimX, 2));
    Angle_Pitch = Misc::toDegrees(atan2f( -(eyeY - aimY), base));
    //Angle_Roll = 0.0;
    KeyState = 0x00;

void EyeCam::onEvent(SDL_Event* event)
    if (event->type == SDL_KEYDOWN)
	    if (event->key.keysym.sym == SDLK_RETURN)
		    std::cout << "X: " << eyeX << '\n';
		    std::cout << "Y: " << eyeY << '\n';
		    std::cout << "Z: " << eyeZ << "\n\n";
		    std::cout << "Heading: " << Angle_Heading << '\n';
		    std::cout << "Pitch: " << Angle_Pitch << '\n';
		    //std::cout << "Roll: " << Angle_Roll << '\n';
	    if (event->key.keysym.sym == SDLK_w)
		    KeyState = KeyState | 0x01;
	    if (event->key.keysym.sym == SDLK_s)
		    KeyState = KeyState | 0x02;
	    if (event->key.keysym.sym == SDLK_a)
		    KeyState = KeyState | 0x04;
	    if (event->key.keysym.sym == SDLK_d)
		    KeyState = KeyState | 0x08;
	    if (event->key.keysym.sym == SDLK_UP)
		    KeyState = KeyState | 0x10;
	    if (event->key.keysym.sym == SDLK_DOWN)
		    KeyState = KeyState | 0x20;
	    if (event->key.keysym.sym == SDLK_LEFT)
		    KeyState = KeyState | 0x40;
	    if (event->key.keysym.sym == SDLK_RIGHT)
		    KeyState = KeyState | 0x80;
    else if (event->type == SDL_KEYUP)
	    if (event->key.keysym.sym == SDLK_w)
		    KeyState = KeyState & 0xFE;
	    if (event->key.keysym.sym == SDLK_s)
		    KeyState = KeyState & 0xFD;
	    if (event->key.keysym.sym == SDLK_a)
		    KeyState = KeyState & 0xFB;
	    if (event->key.keysym.sym == SDLK_d)
		    KeyState = KeyState & 0xF7;
	    if (event->key.keysym.sym == SDLK_UP)
		    KeyState = KeyState & 0xEF;
	    if (event->key.keysym.sym == SDLK_DOWN)
		    KeyState = KeyState & 0xDF;
	    if (event->key.keysym.sym == SDLK_LEFT)
		    KeyState = KeyState & 0xBF;
	    if (event->key.keysym.sym == SDLK_RIGHT)
		    KeyState = KeyState & 0x7F;
void EyeCam::update()
    if (KeyState & 0x01) // w
	    eyeX = eyeX - INCREMENT_FORWARD * sin(Misc::toRadians(Angle_Heading));
	    eyeY = eyeY + INCREMENT_FORWARD * sin(Misc::toRadians(Angle_Pitch));
	    eyeZ = eyeZ - INCREMENT_FORWARD * cos(Misc::toRadians(Angle_Heading));
    if (KeyState & 0x02) // s
	    eyeX = eyeX + INCREMENT_FORWARD * sin(Misc::toRadians(Angle_Heading));
	    eyeY = eyeY - INCREMENT_FORWARD * sin(Misc::toRadians(Angle_Pitch));
	    eyeZ = eyeZ + INCREMENT_FORWARD * cos(Misc::toRadians(Angle_Heading));
    if (KeyState & 0x04) // a
        Angle_Heading = Angle_Heading + INCREMENT_HEADING;
    if (KeyState & 0x08) // d

          Angle_Heading = Angle_Heading - INCREMENT_HEADING;
    if (KeyState & 0x10) // Up
	    Angle_Pitch = Angle_Pitch + INCREMENT_PITCH;
    if (KeyState & 0x20)
	    Angle_Pitch = Angle_Pitch - INCREMENT_PITCH;
    if (KeyState & 0x40) // Left
	    Angle_Roll = Angle_Roll + INCREMENT_ROLL;
    if (KeyState & 0x80) // Right
	    Angle_Roll = Angle_Roll - INCREMENT_ROLL;
    glRotatef(-Angle_Pitch, 1.0, 0, 0);
    glRotatef(-Angle_Heading, 0, 1.0, 0);
    glTranslatef(-eyeX, -eyeY, -eyeZ);
    glRotatef(-Angle_Roll, 0.0, 0.0, 1.0);

The constructor of the class takes the same arguments as gluLookAt() function, except for the Up vector (I've not implemented it yet in my class). The position of the eye in x, y, z coordinates and a point of aim in x, y, z coordinates.

In the constructor, I am calculating two angles, the Heading and the Pitch by using spherical trigonometry and then using these angles to rotate the view accordingly. Please note that, I am not using gluLookAt() function at all in my class.

Then, by using keyboard commands, I am just making changes to the angles to adjust my aim and calculating eye coordinates to adjust my position.

Now, the problem I am having here is that, If I am originally looking down the -ve z- axis and my up is +ve y axis. then I know to adjust my heading I have to Rotate the scene around the y - axis, if I want to adjust pitch I have to Rotate around the x - axis and if I want to adjust roll I have to Rotate around the z-axis. Hence, I am using equation of circle with heading angle to calculate my eyeX and eyeZ and pitch angle to calculate y - axis. But unfortunately, this will only work till I stay in the XZ plane. Any change in the plane, I will not get the desired results.

For example, at the start if I make a 90 degree Roll such that my up now is -ve x-axis, then if I want to Pitch up relative to the camera, I have rotate around the y-axis. Originally I was rotating about the x-axis when roll was 0. Similarly, If I am looking down the -ve z-axis and then roll will perfectly fine because I am rotating around the +ve z axis, however, If I move the camera to aim at the +ve x-axis and then roll it will not work, in that case I have to rotate on the -ve x-axis to make the roll work. I was able to solve this problem by changing the glRotate function for Roll

glRotatef(Angle_Roll, 0, 0, 1);
glRotatef(Angle_Roll, sin(toRadians(Angle_Heading), 0, cos(toRadians(Angle_Heading));

but what if I am looking down the -ve or +ve y-axis, this again will not work as desired and also I try to change the heading then it will automatically affect the roll transformation.

I hope that I am not confusing you guys too much with the my description, please correct me if I am wrong in my assumptions.

So, the bottom line question is, what I need to do make this camera work in every orientation so that it pitchs, rolls, and turns correctly relative to its orientation.

I am not very skilled with mathematics, but I have studied trigonometry and equations of curves and shapes. Please let me know If I need to cover more mathematics in order to implement what I want.

Any input will be appreciated, Thanks.