Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


Nemean Charisma

Member Since 10 Mar 2009
Offline Last Active Mar 30 2012 09:45 PM

Topics I've Started

A* with Binary Heap error

21 March 2012 - 06:01 AM

Hi,

I have just started learning A* and I did successfully to implement with std::vector in C++. However, when I am integrating my Binary Heap implementation, I have problems with POINTER etc and I have spent much time to debug but still could not get a solution of it. May I ask for a little help?

PROBLEM: Whenever I want to access the parent pointer it will give me run time error. The same algorithm (A*) runs smoothly when I am using std::vector.

Inside my CellNode.h

void Print(){
  cout << "Cell Node id : " <<  m_id << " ("<<m_xcoord << " , " << m_zcoord << ")" <<" F = "<< getF()
   << " G = " << getG() << " H = " << getH();
  if ( parent != 0){
   cout << "Cell Node Parent id " << parent->m_id << endl;
  }
  else{
   cout << endl;
  }
}
It enters the if condition but it doesn't have any parent reference. I am pretty much confused with this.

In the implementation I am using Visual Studio 2010 and OpenGL as the graphics rendering. Any kind of help is much appreciated..

Thanks. Posted Image

Min Heap Using C++ Template

05 March 2012 - 07:35 AM

Hi I have tried to implement Binary Heap(Min priority queue) using C++ Templates. But when I test it inside my main program, it cannot compile. Do you have any idea?

File : BHeap.h
/*
This is a class implementation of Binary Heap to optimize A*
It has O(log n) for insertion and deletion to the heap with sorting capability
*/
#ifndef BHEAP_H
#define BHEAP_H
#include <iostream>
#include <string>
using namespace std;
template<class T>
class BHeap
{
public:
BHeap() : DEFAULT_SIZE(100){
  data = new T[DEFAULT_SIZE];
  m_capacity = DEFAULT_SIZE;
  m_count = 0;
}
~BHeap(){
  delete [] data;
}
int size() const{
  return m_count;
}
bool isEmpty() const{
  return m_count == 0;
}
void setCapacity(int newCapacity){
  if ( newCapacity > m_capacity){
   //allocate new capacity
   T *newData = new T[newCapacity];
   memcpy_s(newData, newCapacity, data, m_count);
   m_capacity = newCapacity;
   //copy old data to new data
   data = newData;
  
   delete [] newData;
  }
}
void Add(T item);
void DownHeap();
void UpHeap();

T Peek();
T Remove();
private:
const int DEFAULT_SIZE;
T *data;  //array of data in the heap
int m_count; //count the number of element in the heap
int m_capacity; //to indicate the current capacity in the heap
bool sorted; //boolean variable to test whether it is sorted

int Child1(int idx){
  return (idx << 1) + 1;  //Child 1 index = (2 * parentIndex) + 1
}
int Child2(int idx){
  return (idx << 1) + 2;  //Child 2 index = (2 * parentIndex ) +2
}
int Parent(int idx){
  return (idx - 1 ) >> 1; //Parent index = (childIndex -1 ) / 2
}
//void EnsureSort();
};
//#include "BHeap.cpp"
#endif

File: BHeap.cpp
#include "BHeap.h"
//template<typename T>
//BHeap<T>::BHeap() : DEFAULT_SIZE(100)
//{
// data = new T[DEFAULT_SIZE];
// m_capacity = DEFAULT_SIZE;
// m_count = 0;
//}
//
//template<typename T>
//BHeap<T>::~BHeap()
//{
// delete [] T;
//}
template<class T>
T BHeap<T>::Peek(){
return data[0];
}
template<class T>
void BHeap<T>::Add(T item){
if ( m_count == m_capacity){
  setCapacity(2 * m_capacity);
}
data[m_count] = item;
UpHeap();
m_count++;
}
template<class T>
void BHeap<T>::DownHeap(){
///TODO:
int currentIdx =0;
int n;
T item = data[currentIdx]; //we try to bubble down the root element
while(true){
  int child1, child2;
  child1 = Child1(currentIndex);
  child2 = Child2(currentIndex);
  //find the correct comparison index of child1 and child2
  if ( child1 >= m_count)
   break;
  if ( child2 >= m_count)
   n = child1;
  else{
   n = (data[child1] < data[child2] )? child1 : child2;
  }
  //swap nodes if necessary
  if ( item > data[n]){ //if item is greater than data[n]
   data[currentIndex] = data[n];
   currentIndex = n;
  }
  else{
   break;
  }
}
data[n] = item;
}
template<class T>
void BHeap<T>::UpHeap(){
///TODO:
int childIndex = m_count;
T item = data[childIndex];
int parentIndex = Parent(childIndex);
while (parentIndex > -1 && item < data[parentIndex])
{
  data[childIndex] = data[parentIndex]; //Swap nodes
  childIndex = parentIndex;
  parentIndex = Parent(childIndex);
}
data[childIndex] = item;
}
template<class T>
T BHeap<T>::Remove(){
if ( isEmpty()){
  cout << "Heap is already empty " << endl;
  return NULL;
}
T v = Peek();
m_count--;
data[0] = data[m_count];
data[m_count] = default(T);
DownHeap();
return v;
}

Problem: I cannot use the BHeap implementation:
#include <cstdlib>
#include <time.h>
using namespace std;
#include "BHeap.h"
int main(int argc, char *argv[]){
BHeap< int > heapInt;
srand(time(NULL));
//Add random elements
for(int i = 0 ; i < 10; i++){
  int el = 1 + rand() %100;
  heapInt.Add( el);
  cout << "Element (inserted): "<< el << endl;
}
//Remove all elements
while( heapInt.size() > 0){
  int el = heapInt.Remove();
  cout << "Element (removed): " << el << endl;
}
return 0;
}

FPS jumping movement

30 September 2009 - 06:11 PM

Hi, I want to develop the engine/framework for FPS game. I want to include also a jump movement so that the player can go up at a certain platform(eg. crates) like counter strike. Let say there is a box at position(X,Z)(note:Y axis is upward). How the player can go over the platform(jump on it). I will just need general pseudocode/logic. Thanks

DirectX book and OpenGL book for beginners

26 September 2009 - 12:04 AM

Hi, I'm an intermediate level programmer who know C/C++, Java, and C#. I want to start learning game development. I have searched many topics about this. What I found was that I need to learn DirectX or OpenGL. I am still not sure which one is the first start to learn. I really want to learn both at the same time. Any advice which book is appropriate for beginner DirectX and OpenGL? I just want to grasp the basic/core concept about them so that I can expand my knowledge later.

PARTNERS