Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Makers_F

Member Since 07 Apr 2011
Offline Last Active May 04 2015 10:57 AM

Topics I've Started

Assignement of positions

06 September 2013 - 04:43 AM

Hi everybody

 

I am facing a problem implementing an "algorithm"

I have a list of priority queue (each letter can appear only once per queue, 3 times in total. The priority can be 1, 2 or 3, nothing else), like

First|  1:{X,V,Y} 2:{U}     3:{W}

Second| 1:{Z,U}   2:{V}     3:{}

Third|  1: {}     2:{X}     3:{V}

Fourth| 1:{}      2:{Y,W,Z} 3:{X}

Fifth|  1:{W}     2: {}     3:{U,Y}

Each queue represent a preference toward a position (for example, X has as first preference First, as second preference Third and as third preference Fourth)

But there are some constraints:

  • To each letter can be assigned only one position
  • To each position can be assigned no more than N letters (N is an argument of the function). If less then N letters have a preference for that position, all the letters get placed in that position or a higher preferred one.
  • If in a queue for a position a letter A have an higher priority of a letter B, and B is assigned to that position, then A is assigned to that position too or in a position where A have an higher preference (example: if X is assigned to Fourth, then Y,W,Z are assigned to Fourth too OR  Y,W,Z are placed in a position where they have an higher preference than 2)

Two possible solutions are (with 5 position, the preferences listed as above, and 2 places for each position)

First: [X(1), U(2)]
Second: [Z(1), V(2)]
Third: []
Fourth: [Y(2)]
Fifth: [W(1)]

or

First: [X(1), V(1)]
Second: [Z(1), U(1)]
Third: []
Fourth: [Y(2)]
Fifth: [W(1)]

Between the parenthesis there is which preference have been used to pick that letter

While a wrong one is

First: [X(1), U(2)]
Second: [Z(1), V(2)]
Third: []
Fourth: [Y(2),W(2)]
Fifth: []

because W would like to be placed Fifth, but even if there is space it is placed in a position less preferable.
Note: it is possible that a letter can not be assigned (for example if X, Y, and Z have as only preference First, only 2 can be assigned there.)
I am not sure how to write this algorithm..

Do you have some hints? When I try doing it by hands i end up making lots of comparisons, but i fear cyclic dependency if i implement it like that..


Best design choice for horizzontal scrolling maze boundaries generation

13 October 2012 - 12:46 PM

Hello,

i'm working on an horizontal side scroller game where the player shouldn't touch the walls while it automatically proceed.

Posted Image
(not actual content, this is from an old game)

The player must also catch some objects while proceeding into the maze.
I need to pass to the vertex shader 8 key vertices coordinates, and it will take care to interpolate the position for all the remaining vertices.
in pseudo-code the generator should be
update(elapsed_time) {
	space = velocity * elapsed_time;
	for(i=0; i<8; i++){
		verts[i] -=space;
	}
	if(verts[0]<0) { //out of screen
		shifLeft(verts);
		verts[7] = generate_new_vert();
	}
	total_space +=space; //passed to the fragment shader to correctly repeat the tiled texture
	// the actual code will be a bit different since the X coordinate of the vertices in the array must match the ones of the vertices in the gpu in order to be able in the shader to use the correct value for the correct vertex, but it's just a matter of a few subtractions and checks
}


What is not clear to me is how should i write the (random) generation of the maze.
What i mean is:
  • should i generate what path the player should follow, and create the maze according to it so that the player is almost forced to follow it?
  • or should i just generate the maze with some random parameters(min-max distance between the maze and the obstacles, max player changing direction velocity,...)?
What will make it more controllable? What will give be the best choice in case i want to allow the player to
  • not to force a single route
  • guarantee that, whatever route s/he takes, s/he will be able to always proceed (obviously the "correct" way will be easier that the "wrong" way, but the "wrong" one will give more reward)
Can you maybe point at an analysis of this types of games and what it takes to make them fun?
(i initially started this project as an occasion to learn openGL and shaders, so i didn't really thought too much into the design of the game, but now that i'm working on it i would like to make at least an interesting game to show to some friends, and maybe a basis for a bigger game Posted Image )

Set some specific vertex position, interpolating it for the others

20 September 2012 - 06:26 AM

I have a mesh composed by numerous vertices (600 ± 300 ).

The vertices are simply disposed on 2 parallel line, so that every vertices on a line have the y component equal to the other(they practically are along the sides of a rectangle orthogonal to the screen).
I'm working in a 2D world.

I'm trying to position some vertices in specific points i pass to the shader, and make the other vertices interpolate their position from them.
I generate in my code this matrix

u_specialCoordinatesLocation = {
	x1, x2, x3, x4,
	y1, y2, y3, y4,
	x5, x6, x7, x8,
	y5, y6, y7, y8 };

and pass it to the shader as an uniform (transposing it).

This is the code of the shader. Below i explain it.

/* upperVertexShader*/
/* externally defined:
*   QUALITY_CODE
*   SCREEN_WIDTH
*   SCREEN_HEIGHT
*/

uniform mat4 u_modelViewProjectionMatrix;
uniform vec2 u_playerPosition;
uniform float u_elapsedSeconds;
/*
* mat4 = {
*	{x1, x2, x3, x4},
*	{y1, y2, y3, y4},
*	{x5, ...},
*	{}}
*/

uniform mat4 u_specialCoordinatesPosition;

attribute vec4 a_position;
attribute vec2 a_textureCoordinates;

varying vec2 v_textureCoordinates;
varying vec2 v_playerPosition;
varying vec2 v_pointPosition;

const float ERROR_LIMIT = 0.01;
const float MIN_VALUE = -2e6;
const float MAX_VALUE = 2e6;

float linearInterp(float n0, float n1, float a) {
	 return ((1.0 - a) * n0) + (a * n1);
}

float scurve5(float a) {
	 float a3 = a*a*a;
	 float a4 = a3 * a;
	 float a5 = a4 * a;
	 return (6.0 * a5) - (15.0 * a4) + (10.0 * a3);
}

float min4fv(vec4 vector) {
	 return min(min(vector.x, vector.y),min(vector.z, vector.w));
}

float max4fv(vec4 vector) {
	 return max(max(vector.x, vector.y),max(vector.z, vector.w));
}

/* only return the correct value to offset the vertex if the vertex is one of the ones in the uniform, 0.f otherwise*/
float offsetValue(float Xposition) {
	 float offSet = 0.0;
	 vec4 tmp_vector4;
	 vec4 positionX = vec4(Xposition);

	 // first row
	 // 1.0 if positionX is almost equal to the one specified in the uniform
	 tmp_vector4 = 1.0 - step(ERROR_LIMIT, abs(u_specialCoordinatesPosition[0] - positionX));
	 tmp_vector4 = tmp_vector4 * u_specialCoordinatesPosition[1];
	 offSet += tmp_vector4.x + tmp_vector4.y + tmp_vector4.z + tmp_vector4.w;
	
	 // second row
	 tmp_vector4 = 1.0 - step(ERROR_LIMIT, abs(u_specialCoordinatesPosition[2] - positionX));
	 tmp_vector4 = tmp_vector4 * u_specialCoordinatesPosition[3];
	 offSet += tmp_vector4.x + tmp_vector4.y + tmp_vector4.z + tmp_vector4.w;
	
	 return offSet;
}

vec2 interpolationVertices(float vertexX) {
	 /* .x = left distance
	   * .y = right distance
	   */
	 vec2 distances;

	 /* 0 if at the left of the vertex, else 1*/
	 vec4 left_filter;
	 /* 1 if at the left of the vertex, else 0*/
	 vec4 right_filter;

	 vec4 positionX = vec4(vertexX);
	 /* First row*/
	 left_filter = step(positionX + ERROR_LIMIT, u_specialCoordinatesPosition[0]);
	 // grants that the vertices at the right of the point will not count, by adding only to them a very negative number
	 distances.x = max4fv(u_specialCoordinatesPosition[0] - positionX + left_filter * MIN_VALUE);

	 right_filter = 1.0 - step(positionX - ERROR_LIMIT, u_specialCoordinatesPosition[0]);
	 // grants that the vertices at the left of the point will not count, by adding only to them a very positive number
	 distances.y = min4fv(u_specialCoordinatesPosition[0] - positionX + left_filter * MAX_VALUE);

	 /* Second row*/
	 left_filter = step(positionX + ERROR_LIMIT, u_specialCoordinatesPosition[2]);
	// grants that the vertices at the right of the point will not count, by adding only to them a very negative number
	 distances.x = max(distances.x, max4fv(u_specialCoordinatesPosition[2] - positionX + left_filter * MIN_VALUE));

	 right_filter = 1.0 - step(positionX - ERROR_LIMIT, u_specialCoordinatesPosition[2]);
	 // grants that the vertices at the left of the point will not count, by adding only to them a very positive number
	 distances.y = min(distances.y , min4fv(u_specialCoordinatesPosition[2] - positionX + left_filter * MAX_VALUE));

return distances;
}

float interpolatedValue(float vertexX) {
	 vec2 interpVertices = interpolationVertices(vertexX);
	 vec2 interpValue = vec2(offsetValue(vertexX + interpVertices.x), offsetValue(vertexX + interpVertices.y));
	 float int_value = scurve5(abs((vertexX - interpVertices.x) / (interpVertices.y - interpVertices.x)));
	 return linearInterp(interpValue.x, interpValue.y, int_value);
}

void main(void)
{
	 v_textureCoordinates = a_textureCoordinates;
	 v_playerPosition = u_playerPosition;
	 v_pointPosition = a_position.xy;
	 v_pointPosition.y += interpolatedValue(a_position.x) * (a_position.y) / (a_position.y + 0.0001);
	 vec4 temp_position = u_modelViewProjectionMatrix * vec4(v_pointPosition, a_position.z, a_position.w);
	 gl_Position = temp_position;
}

The vertices y position in the VBO have only 2 different values: 0, or another fixed value (SCREEN_HEIGHT/3).
The vertices that have position.y = 0 shouldn't be moved, so
v_pointPosition.y = interpolatedValue(a_position.x) * (a_position.y) / (a_position.y + 0.0001);

is equal 0 if a_position.y is 0, else is almost equal
v_pointPosition.y = interpolatedValue(a_position.x);

The function
float offsetValue(float Xposition)

should find the value of the Ya in the u_specialCoordinateLocation when passed Xa, 0 otherwise.
The 1.0 - step function is used in order to only account for the correct value each time (since only if the passed vertices distance from the Xa is less than ERROR_LIMIT it will be set to 1.0 and then multiplied by the Ya value)

The function
vec2 interpolationVertices(float vertexX)

should find the Xa and Xb value of the 2 vertices inside the u_specialCoordinateLocation matrix that are nearest to the passed x coordinate.
This is achived by calculating the max of the distance from the left (that should be negative) without taking into account the values bigger than 0
In fact
left_filter = step(positionX + ERROR_LIMIT, u_specialCoordinatesPosition[0]);
will set each component to 0 for each vertex on the left of the passed X position, and to 1.0 otherwise, while
u_specialCoordinatesPosition[0] - positionX + left_filter * MIN_VALUE
will subtract a big value if the filter component is set to 1, thus making impossible to vertices at the right of the position X to contribute once this value is passed to max4fv()

The same is done for the right distance, and then the 2 X coordinates of the 2 vertices are returned.

Finally
float interpolatedValue(float vertexX)
find the 2 vertices "bounding" the passed vertex, retrieve their values, interpolate between them, and return the new position.

I think everything should work, but when i test it on my phone the mesh doesn't show up.
What i'm doing wrong?
Is there a better way of doing it, i must admit that my code isn't really stright forward, and i wish there is a more elegant way?
What do you suggest? (rebuilding the VBO on the cpu and streaming is not a viable option since i would need to do it every frame for 2 meshes of this kind)

Thanks for the help and the patience

[2D] Bonding Box of collision region of 2 rectangles

26 July 2012 - 07:09 AM

Hello,
i'm implementing pixel perfect collision, and in order to make the check faster i want to cull the unused part of the 2 sprites colliding.
I need to find the red area in the pictures (the rectangles can be scaled, rotated, screwed), possibly the one from the last 2 pictures(where the rectangle is parallel to one of the 2 rectangles), but i'm a little confused. I have the vertices in world space, but i can't figure a way to correctly test the right intersections(for each way i think it could be done i can think of a corner case in which it is wrong).

Is there some algorithm to perform this check? I wasn't able to find one, despite the fact it should be a well studied/known subject (at least, i thought 2D collision is a well known and already deeply studied subject..)
Thanks

Attached File  intersection.png   13.79KB   51 downloads
bounding box parallel to the world space axis.
Attached File  intersection2.png   17.36KB   48 downloads
Attached File  intersection3.png   16.63KB   54 downloads
bounding box parallel to the local X axis of one of the 2 rectangles

Ps: i have the transformation matrices of both rectangles

[2D] Bonding Box of collision region of 2 rectangles

24 July 2012 - 12:56 PM

Hello,
i'm implementing pixel perfect collision, and in order to make the check faster i want to cull the unused part of the 2 sprites colliding.
I need to find the red area in the pictures (the rectangles can be scaled, rotated, screwed), possibly the one from the last 2 pictures(where the rectangle is parallel to one of the 2 rectangles), but i'm a little confused. I have the vertices in world space, but i can't figure a way to correctly test the right intersections(for each way i think it could be done i can think of a corner case in which it is wrong).

Is there some algorithm to perform this check? I wasn't able to find one, despite the fact it should be a well studied/known subject (at least, i thought 2D collision is a well known and already deeply studied subject..)

Attached File  intersection.png   13.79KB   57 downloads
bounding box parallel to the world space axis.
Attached File  intersection2.png   17.36KB   57 downloads
Attached File  intersection3.png   16.63KB   49 downloads
bounding box parallel to the local X axis of one of the 2 rectangles
Ps: i have the transformation matrices of both the rectangles

PARTNERS