Jump to content
  • Advertisement

Ateyth

Member
  • Content Count

    7
  • Joined

  • Last visited

Community Reputation

117 Neutral

About Ateyth

  • Rank
    Newbie
  1. Ateyth

    A* heuristic problem

    So here is what i have so far a small application where you can compare the basic A* heuristics. [attachment=28327:screen.png] If any one is interested here is the download link http://www20.zippyshare.com/v/ZRxShHRb/file.html (first time you start the app it can take some while there is no loading screen) I also attached the source(Unity3d C#) maby some one can get some use out of it...    
  2. Ateyth

    A* heuristic problem

    Ok after fixing this.x to this.y i get a realy nice path with your heuristic 1385 steps path length 189 so it need some more steps but it looks very good and the path length seem to be ok to   and no there was no reason for doubling it maby i should take a break ;D   Ok here is a break down of what i got so far   the heuristics [spoiler] public void SetNodeCost(int x, int y, bool diagonal) { if (type == 0) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); float p_dist = 0; if (diagonal == true) { p_dist = Mathf.Sqrt(Mathf.Pow(this.x - parent_node.x, 2) + Mathf.Pow(this.y - parent_node.y, 2)); heuristic_distance = Mathf.Sqrt(dif_x*dif_x + dif_y*dif_y); } else { p_dist = parent_node.distance + 1f; heuristic_distance = (dif_x + dif_y); } distance = parent_node.distance + p_dist; cost = heuristic_distance + distance; } // 1,2,3 lead to the same result ... if (type == 1) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); if (diagonal == true) { distance = parent_node.distance + 1f; if (dif_x > dif_y) { heuristic_distance = dif_y + (dif_x - dif_y); } else { heuristic_distance = dif_x + (dif_y - dif_x); } } else { distance = parent_node.distance + 1f; heuristic_distance = (dif_x + dif_y); } distance = parent_node.distance + distance; cost = heuristic_distance + distance; } if (type == 2) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); distance = parent_node.distance + 1f; heuristic_distance = (dif_x + dif_y); distance = parent_node.distance + distance; cost = heuristic_distance + distance; } if (type == 3) { distance = parent_node.distance + 1f; heuristic_distance = Vector2.Distance (new Vector2(this.x,this.y),new Vector2(x,y)); distance = parent_node.distance + distance; cost = heuristic_distance + distance; } if (type == 4) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); heuristic_distance = Mathf.Sqrt(dif_x*dif_x + dif_y*dif_y); distance = parent_node.distance + 0.5f; cost = heuristic_distance + distance; } if (type == 5) { distance = parent_node.distance + 1f; int dx1 = this.x - x; int dy1 = this.y - y; int dx2 = 0 - x; int dy2 = 0 - y; float cross = Mathf.Abs (dx1 * dy2 - dx2 * dy1); heuristic_distance = (dx1 + dy1); cost = heuristic_distance + distance + cross * 0.01f; } } [/spoiler]   results on map a and b   [spoiler] [attachment=28209:map_a.jpg] [/spoiler] [spoiler] [attachment=28210:map_b.jpg] [/spoiler]
  3. Ateyth

    A* heuristic problem

    Thanks for the help but sadly it work not out with your heuristic the result is   1370 steps and path length = 198   with this one     [spoiler] public void SetNodeCost(int x, int y, bool diagonal) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); // float p_dist = 0; if (diagonal == true) { // p_dist = Mathf.Sqrt(Mathf.Pow(this.x - parent_node.x, 2) + Mathf.Pow(this.x - parent_node.y, 2)); // heuristic_distance = Mathf.Sqrt(dif_x*dif_x + dif_y*dif_y); distance = parent_node.distance + 1.75f; if (dif_x > dif_y) { heuristic_distance = dif_y + (dif_x - dif_y) * 1.4f ; } else { heuristic_distance = dif_x + (dif_y - dif_x) * 1.4f ; } } else { distance = parent_node.distance + 1.75f; heuristic_distance = (dif_x + dif_y); } distance = parent_node.distance + distance; cost = heuristic_distance + distance; } [/spoiler]   1166 steps and path length = 189   so nearly the same result without Math.sqrt and Math.pow :/    
  4. I wrote a small A* algorithm and now cant get it to work like it should i already createt a Topic in the unity board with lot of information so i will put a link here and dont copy and past every thing.     http://forum.unity3d.com/threads/a-heuristic-problem.341721/#post-2210153   Hope some one can tell me what i do wrong cause i am getting out of ideas.   [spoiler] using UnityEngine; using System.Collections; using System.Collections.Generic; public class A_Star : MonoBehaviour { List<A_StarNode> closed_list; List<A_StarNode> open_list; List<A_StarNode> new_nodes_list; List<Vector2> path = new List<Vector2>(); int map_size_x; int map_size_y; int [,] map; private void LoadTestMap() { Object sample= Resources.Load ("map3"); Texture2D pixmap = sample as Texture2D; map_size_x = 50; map_size_y = 50; map = new int[map_size_x,map_size_y]; for (int x = 0; x < map_size_x; x ++) { for (int y = 0; y < map_size_y; y ++) { if(pixmap.GetPixel(x,y).r != 1) { map[x,y] = 1; GameObject obj = Instantiate(Resources.Load ("Cube"),new Vector3(x * 4 + 2, 2,y *4 + 2),Quaternion.AngleAxis(180,new Vector3(0,1,0))) as GameObject; obj.transform.localScale = new Vector3(4,4,4); } } } } void Start () { LoadTestMap (); A_StarNode node = CalculatePath (0, 0, map, 49, 49, true); OptimizePath (node); //Debuging for (int i = 0; i < path.Count; i ++) { GameObject.Instantiate(Resources.Load ("Cube"),new Vector3(path[i].x * 4 + 2,1,path[i].y *4 + 2),Quaternion.AngleAxis(180,new Vector3(0,1,0))); } for (int i = 0; i < path.Count -1; i ++) { Debug.DrawLine (new Vector3 (path [i].x * 4 + 2, 2, path [i].y * 4 + 2), new Vector3 (path [i+ 1].x * 4 + 2, 2, path [i + 1].y * 4 + 2), new Color (0.0f, 0.0f, 0.0f), 10, false); } //------- } public void OptimizePath(A_StarNode node) { int direction = 0; int tmp_direction = 0; while (node.parent_node != null) { node = node.parent_node; if(node.parent_node != null) { if (node.y + 1 == node.parent_node.y) tmp_direction = 360; if (node.x + 1 == node.parent_node.x) tmp_direction = 90; if (node.y - 1 == node.parent_node.y) tmp_direction = 180; if (node.x - 1 == node.parent_node.x) tmp_direction = 270; if (node.y + 1 == node.parent_node.y && node.x + 1 == node.parent_node.x) tmp_direction = 45; if (node.y - 1 == node.parent_node.y && node.x + 1 == node.parent_node.x) tmp_direction = 135; if (node.y - 1 == node.parent_node.y && node.x - 1 == node.parent_node.x) tmp_direction = 225; if (node.y + 1 == node.parent_node.y && node.x - 1 == node.parent_node.x) tmp_direction = 315; } else { path.Add(new Vector2(node.x,node.y)); } if(tmp_direction != direction) { direction = tmp_direction; path.Add(new Vector2(node.x,node.y)); } } } public A_StarNode CalculatePath(int start_x, int start_y, int [,] map, int goal_x, int goal_y, bool allow_diagonal) { closed_list = new List<A_StarNode>(); open_list = new List<A_StarNode>(); new_nodes_list = new List<A_StarNode>(); open_list.Add (new A_StarNode (start_x, start_y, null)); A_StarNode tmp_node; int counter = 0; while (open_list.Count != 0) { counter ++; A_StarNode node = GetCheapestNode(open_list); open_list.Remove (node); if(node.y + 1 < map_size_y) { if(map[node.x,node.y + 1] != 1) { tmp_node = new A_StarNode(node.x, node.y + 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(node.x + 1 < map_size_x) { if(map[node.x + 1,node.y] != 1) { tmp_node = new A_StarNode(node.x + 1, node.y, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(node.y - 1 > 0) { if(map[node.x,node.y - 1] != 1) { tmp_node = new A_StarNode(node.x, node.y - 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(node.x - 1 > 0) { if(map[node.x - 1,node.y] != 1) { tmp_node = new A_StarNode(node.x - 1, node.y, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(allow_diagonal == true) { if(node.x + 1 < map_size_x && node.y + 1 < map_size_y) { if(map[node.x + 1,node.y + 1] != 1) { tmp_node = new A_StarNode(node.x + 1, node.y + 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if( node.x + 1 < map_size_x && node.y - 1 > 0) { if(map[node.x + 1,node.y - 1] != 1) { tmp_node = new A_StarNode(node.x + 1, node.y - 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(node.x - 1 > 0 && node.y - 1 > 0) { if(map[node.x - 1,node.y - 1] != 1) { tmp_node = new A_StarNode(node.x - 1, node.y - 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } if(node.x - 1 > 0 && node.y + 1 < map_size_y) { if(map[node.x - 1,node.y + 1] != 1) { tmp_node = new A_StarNode(node.x - 1, node.y + 1, node); tmp_node.SetNodeCost(goal_x,goal_y,allow_diagonal); new_nodes_list.Add (tmp_node); } } } for(int i = 0; i < new_nodes_list.Count; i ++) { if(new_nodes_list[i].x == goal_x && new_nodes_list[i].y == goal_y) { Debug.Log (counter); return new_nodes_list[i]; } if(ShorterPathIn(open_list,new_nodes_list[i]) == false && ShorterPathIn(closed_list,new_nodes_list[i]) == false) { //Debug float c = (float) counter / 1155f; Debug.DrawLine (new Vector3 (node.x * 4 + 2, 1, node.y * 4 + 2), new Vector3 (new_nodes_list[i].x * 4 + 2, 1 , new_nodes_list[i].y * 4 + 2), new Color (c, c, 1), 10, false); //------------------- open_list.Add (new_nodes_list[i]); } } new_nodes_list.Clear (); closed_list.Add (node); } Debug.Log (counter); return null; } private bool ShorterPathIn(List<A_StarNode> node_list, A_StarNode node) { for (int i = 0; i < node_list.Count; i ++) { if(node.x == node_list[i].x && node.y == node_list[i].y && node_list[i].GetCost() <= node.GetCost()) return true; } return false; } private A_StarNode GetCheapestNode(List<A_StarNode> node_list) { A_StarNode node = null; for (int i = 0; i < node_list.Count; i ++) { if(node == null || node.GetCost() > node_list[i].GetCost()) node = node_list[i]; } return node; } } public class A_StarNode { public int x; public int y; private float cost; private float distance; private float heuristic_distance; public A_StarNode parent_node; public A_StarNode(int x, int y, A_StarNode parent_node) { this.x = x; this.y = y; this.parent_node = parent_node; } // public void SetNodeCost(int x, int y, bool diagonal) // { // distance = parent_node.distance + 0.5f; // int dx1 = this.x - 49; // int dy1 = this.y - 49; // int dx2 = 0 - 49; // int dy2 = 0 - 49; // float cross = Mathf.Abs (dx1 * dy2 - dx2 * dy1); // int dif_x = Mathf.Abs (this.x - x); // int dif_y = Mathf.Abs (this.y - y); // heuristic_distance = (dif_x + dif_y); // cost = heuristic_distance + distance + cross * 0.01f; // //cost = distance + cross * 0.01f; // } public void SetNodeCost(int x, int y, bool diagonal) { int dif_x = Mathf.Abs (this.x - x); int dif_y = Mathf.Abs (this.y - y); if (diagonal == true) { distance = parent_node.GetCost () + 0.1f; if (dif_x > dif_y) { heuristic_distance = dif_y + (dif_x - dif_y); } else { heuristic_distance = dif_x + (dif_y - dif_x); } } else { distance = parent_node.GetCost() + 1f; heuristic_distance = (dif_x + dif_y); } cost = heuristic_distance + distance; } public float GetCost() { return cost; } } [/spoiler]
  5. Ateyth

    Shadow Mapping in Opengl

    first of all THANK YOU GUYS ! it was realy the length() i realy have to face slap my self ;D     light.combined is the projection and view matrix i use a perspectivecamera as a light   http://libgdx.badlogicgames.com/nightlies/docs/api/com/badlogic/gdx/graphics/PerspectiveCamera.html   [attachment=26466:screenshot_normal_3.png]
  6. Ateyth

    Shadow Mapping in Opengl

    Ok here are 2 new Images i hope it is easyer to see what goes wrong.   The depth map [attachment=26464:depth.png]     Camera view [attachment=26463:view.png]     the light is in the lower left corner and points to the torch on the oposit side
  7. Hi i am using Libgdx for game development and found a nice tutorial for Shadow Mapping now i am trying to get my own version to work...   http://www.microbasic.net/tutorials/shadow-mapping/Part-2--one-directional-light.html   So here are the results of my 2 shaders   Depth map from the light [attachment=26441:light_depth.png]   And the render from the camera [attachment=26442:view.png]   as you can see i got a light cone but there are no shadows.   I dont know what i am doing wrong and hope you can give me some hints where my failure is.   And here is the code   First the render class [SPOILER] public class Renderer3D { public static final int depth_texture_i = 0; public static final int diffuse_texture_i = 1; private int shadow_map_size = 4096; private ModelBatch model_batch; private ModelBatch model_depth_batch; private FirstPersonCameraController camera_controller; private PerspectiveCamera camera; private PerspectiveCamera light; private FrameBuffer shadow_FBO; private DepthShader depth_shader; private ShadowShaderView shadow_view_shader; private Texture base_diffuse_texture; public Renderer3D() { // light---------------------------------/ light = new PerspectiveCamera(120, shadow_map_size, shadow_map_size); light.near = 1f; light.far = 50; light.position.set(75,75,5); light.lookAt(10,10,0); light.update(); // Camera--------------------------------/ camera = new PerspectiveCamera(60, Gdx.graphics.getWidth(), Gdx.graphics.getHeight()); camera.near = 1f; camera.far = 300; camera.position.set(75,75,5); camera.lookAt(75,75,0); camera_controller = new FirstPersonCameraController(camera); camera_controller.setVelocity(20); Gdx.input.setInputProcessor(camera_controller); camera.update(); // Shader -------------------------------/ depth_shader = new DepthShader(); depth_shader.init(); shadow_view_shader = new ShadowShaderView(); shadow_view_shader.init(); // ModelBatch----------------------------/ model_batch = new ModelBatch(); model_depth_batch = new ModelBatch(); // FrameBuffer---------------------------/ shadow_FBO = new FrameBuffer(Format.RGBA8888, shadow_map_size, shadow_map_size, false); // Textures------------------------------/ base_diffuse_texture = new Texture(Gdx.files.internal("dungeon tiles/empty_floor.png")); base_diffuse_texture.bind(diffuse_texture_i); } public void render(ArrayList<ModelInstance> instances) { // update render and shader related stuff depth_shader.update(light); shadow_view_shader.update(light); camera_controller.update(); camera.lookAt(camera.position); camera.update(); // render light depth map to Shadow_FBO Gdx.gl.glClearColor(0f, 0f, 0f, 1f); Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT| GL20.GL_DEPTH_BUFFER_BIT); shadow_FBO.begin(); model_depth_batch.begin(light); model_depth_batch.render(instances,depth_shader); model_depth_batch.end(); if(Gdx.input.isKeyJustPressed(Keys.SPACE) == true) { ScreenshotFactory.saveScreenshot(shadow_map_size, shadow_map_size, "depth"); } shadow_FBO.end(); shadow_FBO.getColorBufferTexture().bind(depth_texture_i); // render from camera view Gdx.gl.glClearColor(0.4f, 0.4f, 0.4f, 0.4f); Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT| GL20.GL_DEPTH_BUFFER_BIT); model_batch.begin(camera); model_batch.render(instances,shadow_view_shader); model_batch.end(); if(Gdx.input.isKeyJustPressed(Keys.SPACE) == true) { ScreenshotFactory.saveScreenshot( Gdx.graphics.getWidth(), Gdx.graphics.getHeight(), "normal"); } } } [/SPOILER]   vertex shader for light [SPOILER] #ifdef GL_ES #define LOWP lowp #define MED mediump #define HIGH highp precision mediump float; #else #define MED #define LOWP #define HIGH #endif attribute vec3 a_position; uniform mat4 u_projTrans; uniform mat4 u_worldTrans; uniform mat4 u_LightTrans; varying vec4 v_position; varying vec4 v_position_LightTrans; void main() { v_position = u_worldTrans*vec4(a_position, 1.0); v_position_LightTrans = u_LightTrans*v_position; gl_Position = u_projTrans *v_position; } [/SPOILER]   fragment shader for light [SPOILER] #ifdef GL_ES #define LOWP lowp #define MED mediump #define HIGH highp precision mediump float; #else #define MED #define LOWP #define HIGH #endif uniform float u_cameraFar; uniform vec3 u_lightPositon; varying vec4 v_position; varying vec4 v_position_LightTrans; void main() { // Simple depth calculation, just the length of the vector light-current position float length = length(v_position.xyz-u_lightPositon)/u_cameraFar; gl_FragColor = vec4(1.0-length); } [/SPOILER]   the shader class for the light [SPOILER] public class DepthShader implements Shader { ShaderProgram program; Camera camera; Camera light; RenderContext context; int u_projTrans; int u_worldTrans; int u_lightPositon; int u_cameraFar; int u_LightTrans; @Override public void init () { String vert = Gdx.files.internal("data/DepthShader.vert").readString(); String frag = Gdx.files.internal("data/DepthShader.frag").readString(); program = new ShaderProgram(vert, frag); if (!program.isCompiled())throw new GdxRuntimeException(program.getLog()); u_projTrans = program.getUniformLocation("u_projTrans"); u_worldTrans = program.getUniformLocation("u_worldTrans"); u_lightPositon = program.getUniformLocation("u_lightPositon"); u_cameraFar = program.getUniformLocation("u_cameraFar"); u_LightTrans = program.getUniformLocation("u_LightTrans"); } @Override public void dispose () { program.dispose(); } @Override public void begin (Camera camera, RenderContext context) { this.camera = camera; this.context = context; program.begin(); context.setDepthTest(GL20.GL_LEQUAL); context.setCullFace(GL20.GL_BACK); } public void update(Camera light) { this.light = light; } @Override public void render (Renderable renderable) { program.setUniformMatrix(u_projTrans, camera.combined); program.setUniformf(u_lightPositon, light.position); program.setUniformMatrix(u_LightTrans, light.combined); program.setUniformf(u_cameraFar, light.far); program.setUniformMatrix(u_worldTrans, renderable.worldTransform); renderable.mesh.render(program, renderable.primitiveType, renderable.meshPartOffset, renderable.meshPartSize); } @Override public void end () { program.end(); } @Override public int compareTo (Shader other) { return 0; } @Override public boolean canRender (Renderable instance) { return true; } } [/SPOILER]   Vertex Shader for camera [SPOILER] #ifdef GL_ES #define LOWP lowp #define MED mediump #define HIGH highp precision mediump float; #else #define MED #define LOWP #define HIGH #endif attribute vec3 a_position; attribute vec2 a_texCoord0; uniform mat4 u_projTrans; uniform mat4 u_worldTrans; uniform mat4 u_LightTrans; varying vec2 v_texCoords0; varying vec4 v_position; varying vec4 v_position_LightTrans; void main() { v_texCoords0 = a_texCoord0; v_position = u_worldTrans*vec4(a_position, 1.0); v_position_LightTrans = u_LightTrans*v_position; gl_Position = u_projTrans *v_position; } [/SPOILER]   Fragment Shader for camera [SPOILER] #ifdef GL_ES #define LOWP lowp #define MED mediump #define HIGH highp precision mediump float; #else #define MED #define LOWP #define HIGH #endif uniform float u_cameraFar; uniform vec3 u_lightPositon; uniform sampler2D u_depthMap; uniform sampler2D u_text; varying vec2 v_texCoords0; varying vec4 v_position; varying vec4 v_position_LightTrans; void main() { vec4 finalColor = texture2D(u_text, v_texCoords0); vec3 depth = length(v_position_LightTrans.xyz / v_position_LightTrans.w)*0.5+0.5; if (v_position_LightTrans.z>=0.0 && (depth.x >= 0.0) && (depth.x <= 1.0) && (depth.y >= 0.0) && (depth.y <= 1.0) ) { float lenToLight=length(v_position.xyz-u_lightPositon)/u_cameraFar; float lenDepthMap= texture2D(u_depthMap, depth.xy).a; // If can not be viewed by light > shadows if(lenDepthMap<lenToLight-0.005) { finalColor.rgb*=0.4; } else { finalColor.rgb*=0.4+0.6*(1.0-lenToLight); } } else { finalColor.rgb*=0.4; } gl_FragColor = finalColor; } [/SPOILER]   the shader class for the camera [SPOILER] public class ShadowShaderView implements Shader { ShaderProgram program; Camera camera; Camera light; RenderContext context; int u_projTrans; int u_worldTrans; int u_lightPositon; int u_cameraFar; int u_LightTrans; @Override public void init () { String vert = Gdx.files.internal("data/DepthShaderView.vert").readString(); String frag = Gdx.files.internal("data/DepthShaderView.frag").readString(); program = new ShaderProgram(vert, frag); if (!program.isCompiled())throw new GdxRuntimeException(program.getLog()); u_projTrans = program.getUniformLocation("u_projTrans"); u_worldTrans = program.getUniformLocation("u_worldTrans"); u_lightPositon = program.getUniformLocation("u_lightPositon"); u_cameraFar = program.getUniformLocation("u_cameraFar"); u_LightTrans = program.getUniformLocation("u_LightTrans"); } @Override public void dispose () { program.dispose(); } @Override public void begin (Camera camera, RenderContext context) { this.camera = camera; this.context = context; program.begin(); context.setDepthTest(GL20.GL_LEQUAL); context.setCullFace(GL20.GL_BACK); } public void update(Camera light) { this.light = light; } @Override public void render (Renderable renderable) { program.setUniformMatrix(u_projTrans, camera.combined); program.setUniformf(u_lightPositon, light.position); program.setUniformMatrix(u_LightTrans, light.combined); program.setUniformi("u_depthMap", Renderer3D.depth_texture_i); program.setUniformi("u_text" , Renderer3D.diffuse_texture_i); program.setUniformf(u_cameraFar, light.far); program.setUniformMatrix(u_worldTrans, renderable.worldTransform); renderable.mesh.render(program, renderable.primitiveType, renderable.meshPartOffset, renderable.meshPartSize); } @Override public void end () { program.end(); } @Override public int compareTo (Shader other) { return 0; } @Override public boolean canRender (Renderable instance) { return true; } } [/SPOILER]
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!