Makers_F

It doesn't matter. It depends on the coordinate system. It can even be the centre. Try to understand the concepts, not the single example! Replace "left bottom" with "top-left", "center", "a point a hundred times the dimension of the sprite away from the sprite" and it will still be corrected! The transformation translate a whatever point in the local coordinate system to the world coordinate system

The position is taken into account by the transformation. The transformation matrix contains the translation, rotation, skew and scale. This means that if you multiply {0,0} (the left bottom corner of your sprite) for the matrix of this sprite, it will give the coordinates of the point in the world coordinate system which touches the left bottom corner of your sprite. This is valid for every point of the sprite

I searched for a solution to the same problem a few months ago. I found a fantastic work from microsoft.
It is the fastest pixel perfect collision idea i have found, and support whatever affine transformation(but you need a transformation matrix)


http://xbox.create.msdn.com/en-US/education/catalog/tutorial/collision_2d_perpixel_transformed


The standard idea to support rotations is to work in the local space of the sprite A and bring the sprite B in local A space.

Then, microsoft suggests to transform the X and Y versor of A local space to B's one, and then just add the transformed versors to the B's local transofrmation currently checked coordinate, in order to make 2 additions instead of a matrix multiplication


The archive in the link contains a better explaination, but i hope you can get a grasp of what i meant.


Here's my implementation. It works really nice even on mobile hardware. Obviously you can't abuse pixel perfect collision
https://github.com/MakersF/AndEngineCollisionsExtension/blob/master/src/com/makersf/andengine/extension/collisions/pixelperfect/PixelPerfectCollisionChecker.java

As waterlimon stated, use pixel perfect collision only if it is the only one that make sense (you have sprites that should have holes and you must check against point that can potentially be smaller that that holes. Or something extremely unregular)

Ok, since swig has a bit of problems with c++, i followed another way.

I created a dll using a C implementation of perlin noise (python can load c written dll without any problems. With c++ it has some problems because of the name of the functions, but if them can be exported with extern C there wouldn't be any problem to load libnoise dll, but i haven't tryed)

Here the .c file

/* Coherent noise function over 1, 2 or 3 dimensions */
/* (copyright Ken Perlin) */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "perlin.h"
#define random rand
static int p[B + B + 2];
static double g3[B + B + 2][3];
static double g2[B + B + 2][2];
static double g1[B + B + 2];
static int start = 1;

double noise1(double arg)
{
   int bx0, bx1;
   double rx0, rx1, sx, t, u, v, vec[1];

   vec[0] = arg;
   if (start) {
  	start = 0;
  	init();
   }

   setup(0,bx0,bx1,rx0,rx1);

   sx = s_curve(rx0);
   u = rx0 * g1[ p[ bx0 ] ];
   v = rx1 * g1[ p[ bx1 ] ];

   return(lerp(sx, u, v));
}

double noise2(double vec[2])
{
   int bx0, bx1, by0, by1, b00, b10, b01, b11;
   double rx0, rx1, ry0, ry1, *q, sx, sy, a, b, t, u, v;
   int i, j;

   if (start) {
  	start = 0;
  	init();
   }

   setup(0, bx0,bx1, rx0,rx1);
   setup(1, by0,by1, ry0,ry1);

   i = p[ bx0 ];
   j = p[ bx1 ];

   b00 = p[ i + by0 ];
   b10 = p[ j + by0 ];
   b01 = p[ i + by1 ];
   b11 = p[ j + by1 ];

   sx = s_curve(rx0);
   sy = s_curve(ry0);

   q = g2[ b00 ] ; u = at2(rx0,ry0);
   q = g2[ b10 ] ; v = at2(rx1,ry0);
   a = lerp(sx, u, v);

   q = g2[ b01 ] ; u = at2(rx0,ry1);
   q = g2[ b11 ] ; v = at2(rx1,ry1);
   b = lerp(sx, u, v);

   return lerp(sy, a, b);
}

double noise3(double vec[3])
{
   int bx0, bx1, by0, by1, bz0, bz1, b00, b10, b01, b11;
   double rx0, rx1, ry0, ry1, rz0, rz1, *q, sy, sz, a, b, c, d, t, u, v;
   int i, j;

   if (start) {
  	start = 0;
  	init();
   }

   setup(0, bx0,bx1, rx0,rx1);
   setup(1, by0,by1, ry0,ry1);
   setup(2, bz0,bz1, rz0,rz1);

   i = p[ bx0 ];
   j = p[ bx1 ];

   b00 = p[ i + by0 ];
   b10 = p[ j + by0 ];
   b01 = p[ i + by1 ];
   b11 = p[ j + by1 ];

   t  = s_curve(rx0);
   sy = s_curve(ry0);
   sz = s_curve(rz0);

   q = g3[ b00 + bz0 ] ; u = at3(rx0,ry0,rz0);
   q = g3[ b10 + bz0 ] ; v = at3(rx1,ry0,rz0);
   a = lerp(t, u, v);

   q = g3[ b01 + bz0 ] ; u = at3(rx0,ry1,rz0);
   q = g3[ b11 + bz0 ] ; v = at3(rx1,ry1,rz0);
   b = lerp(t, u, v);

   c = lerp(sy, a, b);

   q = g3[ b00 + bz1 ] ; u = at3(rx0,ry0,rz1);
   q = g3[ b10 + bz1 ] ; v = at3(rx1,ry0,rz1);
   a = lerp(t, u, v);

   q = g3[ b01 + bz1 ] ; u = at3(rx0,ry1,rz1);
   q = g3[ b11 + bz1 ] ; v = at3(rx1,ry1,rz1);
   b = lerp(t, u, v);

   d = lerp(sy, a, b);

   return lerp(sz, c, d);
}

void normalize2(double v[2])
{
   double s;

   s = sqrt(v[0] * v[0] + v[1] * v[1]);
   v[0] = v[0] / s;
   v[1] = v[1] / s;
}

void normalize3(double v[3])
{
   double s;

   s = sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
   v[0] = v[0] / s;
   v[1] = v[1] / s;
   v[2] = v[2] / s;
}

void init(void)
{
   int i, j, k;

   for (i = 0 ; i < B ; i++) {
  	p[i] = i;
  	g1[i] = (double)((random() % (B + B)) - B) / B;

  	for (j = 0 ; j < 2 ; j++)
 		g2[i][j] = (double)((random() % (B + B)) - B) / B;
  	normalize2(g2[i]);

  	for (j = 0 ; j < 3 ; j++)
 		g3[i][j] = (double)((random() % (B + B)) - B) / B;
  	normalize3(g3[i]);
   }

   while (--i) {
  	k = p[i];
  	p[i] = p[j = random() % B];
  	p[j] = k;
   }

   for (i = 0 ; i < B + 2 ; i++) {
  	p[B + i] = p[i];
  	g1[B + i] = g1[i];
  	for (j = 0 ; j < 2 ; j++)
 		g2[B + i][j] = g2[i][j];
  	for (j = 0 ; j < 3 ; j++)
 		g3[B + i][j] = g3[i][j];
   }
}

/* --- My harmonic summing functions - PDB --------------------------*/

/*
   In what follows "alpha" is the weight when the sum is formed.
   Typically it is 2, As this approaches 1 the function is noisier.
   "beta" is the harmonic scaling/spacing, typically 2.
*/

double PerlinNoise1D(double x,double alpha,double beta,int n)
{
   int i;
   double val,sum = 0;
   double p,scale = 1;

   p = x;
   for (i=0;i<n;i++) {
  	val = noise1(p);
  	sum += val / scale;
  	scale *= alpha;
  	p *= beta;
   }
   return(sum);
}

double PerlinNoise2D(double x,double y,double alpha,double beta,int n)
{
   int i;
   double val,sum = 0;
   double p[2],scale = 1;

   p[0] = x;
   p[1] = y;
   for (i=0;i<n;i++) {
  	val = noise2(p);
  	sum += val / scale;
  	scale *= alpha;
  	p[0] *= beta;
  	p[1] *= beta;
   }
   return(sum);
}

double PerlinNoise3D(double x,double y,double z,double alpha,double beta,int n)
{
   int i;
   double val,sum = 0;
   double p[3],scale = 1;

   p[0] = x;
   p[1] = y;
   p[2] = z;
   for (i=0;i<n;i++) {
  	val = noise3(p);
  	sum += val / scale;
  	scale *= alpha;
  	p[0] *= beta;
  	p[1] *= beta;
  	p[2] *= beta;
   }
   return(sum);
}

Here the .h file

#define B 0x100
#define BM 0xff
#define N 0x1000
#define NP 12   /* 2^N */
#define NM 0xfff

#define s_curve(t) ( t * t * (3. - 2. * t) )
#define lerp(t, a, b) ( a + t * (b - a) )
#define setup(i,b0,b1,r0,r1)\
    	t = vec[i] + N;\
    	b0 = ((int)t) & BM;\
    	b1 = (b0+1) & BM;\
    	r0 = t - (int)t;\
    	r1 = r0 - 1.;
#define at2(rx,ry) ( rx * q[0] + ry * q[1] )
#define at3(rx,ry,rz) ( rx * q[0] + ry * q[1] + rz * q[2] )

#ifdef BUILDING_NOW_DLL
#define DLL_DECLSPEC __declspec(dllexport)
#else
#define DLL_DECLSPEC __declspec(dllimport)
#endif

void init(void);
double noise1(double);
double noise2(double *);
double noise3(double *);
void normalize3(double *);
void normalize2(double *);

double DLL_DECLSPEC PerlinNoise1D(double,double,double,int);
double DLL_DECLSPEC PerlinNoise2D(double,double,double,double,int);
double DLL_DECLSPEC PerlinNoise3D(double,double,double,double,double,int);

Here the python module that "wrap" the library

import ctypes

class Perlin_Noise():
	
	#using the implementation described here
	# http://paulbourke.net/texture_colour/perlin/
	def __init__(self, path_to_library , weight = 2.0, spacing = 2.0, zoom = 10, octaves = 5.0):
		self._libc= ctypes.cdll.LoadLibrary(path_to_library)
		#Typically it is 2, As this approaches 1 the function is noisier.
		self._sum_weight = weight
		#It is the harmonic scaling/spacing, typically 2
		self._harmonic_spacing = spacing
		#The zoom of the generate texture
		self._zoom = zoom
		#The number of octaves(note: high values can bringh to overflow[caused by python])
		self._octaves = octaves
		
		self._libc.PerlinNoise1D.restype = ctypes.c_double
		self._libc.PerlinNoise2D.restype = ctypes.c_double
		self._libc.PerlinNoise3D.restype = ctypes.c_double
		
		self._last1D = None
		self._last2D = None
		self._last3d = None
	
	def setSumWeight(self, weight):
		self._sum_weight = weight
	
	def setHarmonicSpacing(self, spacing):
		self._harmonic_spacing = spacing
	
	def setZoom(self, zoom):
		self._zoom = zoom
	
	def setOctaves(self, octaves):
		self._octaves = octaves
	
	def getLast1D(self):
		if hasattr(self, "_last1D"):
			return self._last1D
		else:
			return None
	
	def getLast2D(self):
		if hasattr(self, "_last2D"):
			return self._last2D
		else:
			return None
	
	def getLast3D(self):
		if hasattr(self, "_last3D"):
			return self._last3D
		else:
			return None
	
	def noise1D(self, x):
		self._last1D = self._libc.PerlinNoise1D(
							             ctypes.c_double(x / self._zoom), 
							             ctypes.c_double(self._sum_weight), 
							             ctypes.c_double(self._harmonic_spacing), 
							             ctypes.c_int(self._octaves)
							             )
		return  self._last1D
	
	def noise2D(self, x , y):
		self._last2D = self._libc.PerlinNoise2D(
							             ctypes.c_double(x / self._zoom),
							             ctypes.c_double(y / self._zoom), 
							             ctypes.c_double(self._sum_weight), 
							             ctypes.c_double(self._harmonic_spacing), 
							             ctypes.c_int(self._octaves)
							             )
		return self._last2D
	
	def noise3D(self, x , y, z):
		self._last3D = self._libc.PerlinNoise3D(
							             ctypes.c_double(x / self._zoom),
							             ctypes.c_double(y / self._zoom), 
							             ctypes.c_double(z / self._zoom), 
							             ctypes.c_double(self._sum_weight), 
							             ctypes.c_double(self._harmonic_spacing), 
							             ctypes.c_int(self._octaves)
							             )
		return self._last3D

Here a script to try if the module works

import perlin_noise
import math
from PIL import Image

w , h = 1000, 1000
new_noise = perlin_noise.Perlin_Noise("perlin.dll", 1, 3, 10, 0)
new_noise.setSumWeight(2)
new_noise.setHarmonicSpacing(200)
new_noise.setZoom(5)
new_noise.setOctaves(1)

image = Image.new("L", (w,h))
pix = image.load()
for i in range(0,w):
	for l in range(0,h):
		x = i+math.sin(i)
		y = l+math.cos(l)
		pix[i,l] = ( (new_noise.noise2D(x,y) + 1) / 2 ) * 255
image.save("noise.jpeg")

new_noise.noise1D(new_noise.getLast2D())
new_noise.noise3D(new_noise.getLast1D(), new_noise.getLast2D(), x+y)
new_noise.getLast3D()

Here part of the code in used to generate the coords of the trees:

sector = square["mysector"]
  vegetation = Perlin_Noise(g.expandPath("//") + "Perlin" + os.path.sep + "perlin.dll",2, 1000, 10, 1)
  # tree_number = (max_trees_per_square_meter) * size_of_the_tile || in this case max 1 tree per 3 square meter
  tree_number = int( abs( vegetation.noise2D( sector[0], sector[1] ) / 3 ) * 16 * 16)
  rand = random.Random()
  rand.seed(hash(tuple(sector)))
  for k in range(0, tree_number):
   x = (rand.random() -0.5 ) * bge.size
   y = (rand.random() - 0.5) * bge.size
  #make it relative to the center of the tile
   x = square.worldPosition[0] + x
   y = square.worldPosition[1] + y

I added all this code so that if someone will have the same problem can find here a good way to start from. I managed to create the system for loading the trees, now it will just need polishing and a bit of improvement. I'm sorry i dind't managed to use the libnoise library, it seams well coded and feature complete, if someone have any hints about how to export its functions as C functions let me know

Thanks very much to who made this possible helping me, now i'm a little less noob