Goal finding: I just need the name of an algorithm
-
Hi, I need to find a goal given the following conditions -I only know my 4 surroundings (N,W,S,E): they can be empty or an obstacle -I know the goal coordinates (x,y) -I know my coordinates I know bug-2 (and bug-1) are complete algorithms (they always find the goal). But it is really bad in some maps with large obstacles. My questions are two. 1. How come there arent quick and well-known solutions to this? Ive been googling for ages and I just find theoretical papers, full of blabla and no pseudocode. 2. A* wouldnt work for this because of my first restriction, right? Thanks
-
Hi, I need to find a goal given the following conditions -I only know my 4 surroundings (N,W,S,E): they can be empty or an obstacle -I know the goal coordinates (x,y) -I know my coordinates I know bug-2 (and bug-1) are complete algorithms (they always find the goal). But it is really bad in some maps with large obstacles. My questions are two. 1. How come there arent quick and well-known solutions to this? Ive been googling for ages and I just find theoretical papers, full of blabla and no pseudocode. 2. A* wouldnt work for this because of my first restriction, right? Thanks
I'm sure A* would work - all it requires is to know if a neighbouring tile is walkable or not, and then a cost for moving there. (Sidenote: you could substitute this for simply assigning a cost to moving across each tile and make impassable obstacles have infinite cost?) Anyway, here's a good A* link: http://www.policyalmanac.org/games/aStarTutorial.htm This is 8-directional, but it will work exactly the same in 4-directional.
-
Hi, I need to find a goal given the following conditions -I only know my 4 surroundings (N,W,S,E): they can be empty or an obstacle -I know the goal coordinates (x,y) -I know my coordinates I know bug-2 (and bug-1) are complete algorithms (they always find the goal). But it is really bad in some maps with large obstacles. My questions are two. 1. How come there arent quick and well-known solutions to this? Ive been googling for ages and I just find theoretical papers, full of blabla and no pseudocode. 2. A* wouldnt work for this because of my first restriction, right? Thanks
Hi You can represent this as a Graph-problem(some kind of shortest path algorithm) You can apply these restrictions while moving 1 . Trace your current path, if the new slot is in the current path ignore that to avoid a loop 2 . Mark the positions in which no further movements are possible so that we can ignore that. 3 . If we have no further move retract your move using a stack Back-tracking may not be an optimal solution, but you can apply some restrictions to improve it Thanks