Pathfinder
A pathfinding library written in Swift
Ilija Tovilo (@IlijaTovilo) on Twitter
Can we get people to post code of simple, optimized implementations of the A* pathfinding algorithm, in every single language?
This is mostly for fun and to play with what stackoverflow itself is capable of... although I actually am interested in getting an ActionScript 3 version of this.
But the idea is that this "Question" will continue to be updated eternally into the future, even as different programming languages are created!
I don't know of any other place online where you can see pseudocode "translated" into many (much less every) different language. Seems like it's a worthwhile resource, and while not necessarily what this site was designed for, there's no harm in trying it out and seeing if it turns out to be a worthwhile thing that stackoverflow could be used for!
Source: (StackOverflow)
I need to find out all the files and folders whose name has search string as their prefix within the current directory and also within its child directory. Same like finder done searching.
I have tried using NSFileManager but it get results only for current directory.
Using NSTask I am able to get file/ folder within current directory and also within child directories. but the problem is that i am not able to fetch files and folders in a single search. I can only search for files or folders not for both simultaneously.
Also if i use NStask i am not able to get output by some interval. it return me result when NStask finished. I already tried to use notification NSFileHandleDataAvailableNotification, but it return me data when task completed.
Is there any other way, So that i can search for Directory and files. One other Application Path Finder is already done this. If any one have idea for this. Please help me
Thanks
Source: (StackOverflow)
I am experimenting with towerjs. I just followed the instructions to create a project.
npm install tower -g
npm install grunt -g
mongod
tower new app
cd app
npm install
And when I try to start the server for the project I get the following error:
GT@ubuntu:~/work/app$ node server.js
node.js:201
throw e; // process.nextTick error, or 'error' event on first tick
^
Error: ENOENT, no such file or directory '/home/GT/work/app/config/localesundefineden.coffee'
at Object.statSync (fs.js:422:18)
at Function.stat (/home/GT/work/app/node_modules/pathfinder/lib/pathfinder/file.js:21:17)
at Function.isDirectory (/home/GT/work/app/node_modules/pathfinder/lib/pathfinder/file.js:165:19)
at Function.isFile (/home/GT/work/app/node_modules/pathfinder/lib/pathfinder/file.js:169:20)
at Function.files (/home/GT/work/app/node_modules/pathfinder/lib/pathfinder/file.js:137:18)
at [object Object].<anonymous> (/home/GT/work/app/node_modules/tower/packages/tower-application/server/application.coffee:157:22)
at /home/GT/work/app/node_modules/tower/packages/tower-support/shared/callbacks.coffee:141:28
at /home/GT/work/app/node_modules/tower/packages/tower-support/shared/shared.coffee:307:22
at SupportCallback.run (/home/GT/work/app/node_modules/tower/packages/tower-support/shared/callbacks.coffee:204:18)
at /home/GT/work/app/node_modules/tower/packages/tower-support/shared/callbacks.coffee:110:25
Any help would be appreciated.
Thanks
UPDATE:
With further investigation
_path = require('path')
_path.sep
seems to return undefined. Why would it not return /?
Source: (StackOverflow)
I have Path finder set up as my default file browser on my OSX Yosemite mbp.
So most application open a Path Finder window when they show my a File, but not IDEA.
When I choose the "Reveal in Finder"-action on a file it always open a new finder window, which is kind of annoying because copying from a Pathfinder window to a Finder window is not working.
Is there a way/setting to tell IDEA to use Pathfinder?
Source: (StackOverflow)
I need to create an AI for an object that is avoiding other simple AIs. The enemy is easy to predict. How could I create a pathfinder that finds the fastest path never going within 3 units of the enemy AI?
Source: (StackOverflow)
How does the pathfinder algorithm work in fpga routing? I have an oral exam on this topic next week... so Can anyone explain the two iterations clearly with an example may be ...thanks in advance
Source: (StackOverflow)
I have an assignment to write a Prolog program that lists paths between two Underground (subway) stations, but it should favour the paths with less line changes (it should stay as long as possible in the same line before switching lines).
I've come up with a mock scenario and this code, while it correctly lists some paths (I know I still have to code the cycle detection), does not prioritise same-line segments as it should.
My router is:
route(X,Y,[drive(X,Y,L)],_) :- road(X,Y,L).
%route(From, To, Directions, Lines_Visited).
route(X,Y,[drive(X,Z,L)|R],Ls) :-
take(Ls,L,_), %prioritise same-line paths
road(X,Z,L),
route(Z,Y,R,Ls), !.
route(X,Y,[drive(X,Z,L)|R],Ls) :-
road(X,Z,L), %if no same-line pathes exist, try different line
route(Z,Y,R,[Ls|L]).
Where take/3 is
take([H|T], H, T).
One test scenario would be:
road(a,b,x).
road(b,c,x).
road(c,d,x).
road(d,e,x).
road(e,f,x).
road(b,f,y).
road(f,g,x).
%a - b - c - d - e - f - g
% |_______________|
If I try route(a,f,X). I'd get the path a -> b -> f , which changes lines once, and THEN the one-line path a->b->c->d->e->f.
Apparently my prioritisation is not working and I can't come up with a different way of doing it. Can someone please shed some light and point me to a direction to solve this more efficiently?
Source: (StackOverflow)
I'm trying to create an implementation of Dijkstra's pathfinding which seems to be working great, apart from if I ask it to create a route that starts and ends in the same place.
JSFiddle: http://jsfiddle.net/Lt6b4ecr/
I need it to pick the lowest possible weighted route which should be B-C-E-B but instead it just sits at 0 :(
My graph is designed as so:
var graph = {
A: { B: '5', D: '5', E: '7' },
B: { C: '4' },
C: { D: '8', E: '2' },
D: { C: '8', E: '6' },
E: { B: '3' }};
and worth noting that the connections/edges are to be treated as one way only.
Any help would be massively appreciated!
Source: (StackOverflow)
I'm trying to speed up my A* implementation (really bad lag just at 10x10 grid!) and the worst performance hit is likely coming from this function:
public Vector2 CoordsToIndex(Vector2 coords)
{
for (int i = 0; i < mapCols; ++i)
{
for (int j = 0; j < mapRows; ++j)
{
if (coords.X >= i * map[0, 0].length &&
coords.X < i * map[0, 0].length + map[0, 0].length)
{
indexi = i;
}
if (coords.Y >= j * map[0, 0].height &&
coords.Y < j * map[0, 0].height + map[0, 0].height)
{
indexj = j;
}
}
}
return new Vector2(indexi, indexj);
}
My original implementation of it isn't quite right, but if I can get this working instead it will speed things up a lot (I use this function constantly):
// The below math isn't quite right
indexi = (int)((coords.X - (map[0, 0].length / 2)) / map[0, 0].length) - 1;
indexj = (int)((coords.Y - (map[0, 0].height / 2)) / map[0, 0].height) - 1;
if (indexi < 0)
{
indexi = 0;
}
if (indexj < 0)
{
indexj = 0;
}
map[0, 0].length is the length of the tile, and map[0, 0].height is the height of the tile. All tiles are uniform.
It has to be possible to come up with a formula to calculate this but I'm not really certain as to what it would be. Any pointers/help/answers would be appreciated!
EDIT: Er...actually I think the problem might be subtracting the length or height divided by two. That's fine for tile nodes since I store their position as the center of the tile, but for this it would give the wrong tile back...maybe that's the problem...checking.
EDIT: Ah..it's that AND remove the -1. Man I get so confused, funny how I spent about two hours last night totally confused by this and then seconds after finally posting for help the answer comes to me in a flash.
SOLUTION:
public Vector2 CoordsToIndex(Vector2 coords)
{
int indexi = (int)(coords.X / map[0, 0].length);
int indexj = (int)(coords.Y / map[0, 0].height);
return new Vector2(indexi, indexj);
}
That looks so much better.
Source: (StackOverflow)
I wanna do navigation/A* on a QuadTree.
I already implemented a QuadTree, or at least what I think is a QuadTree. Meanwhile I have seen some where also the inner nodes contain elements. With mine the inner nodes only link to their children and the elements are stored in collections in leaf nodes.
While each node links to its parent there are (currently) no links to the neighbors, neither siblings nor nodes of other branches. Elements are regions and not just points.
I have also seen A* quite some time on grids and even a demo on QuadTree, but this was without details.
I guess the main question is how do I quickly get to my neighbors?
I am not sure if I should keep the leafs linked to each other. But this would be a hell of a job as the tree is dynamic as the elements update their position. It would also need need some king of dynamic collection for the links as depending on the node size a big leaf can have a lot of small leafs on one direction (e.g. East). The effort to update this seems quite huge, even currently don't know how I would do it.
Thx n rgds
Source: (StackOverflow)
I have an SVG object with a floor map which is made from a creator user and I want to find dynamically the shortest path between 2 points on this object.
Dijkstra algorithm is the better solution for finding shortest path into a graph but this solution required the knowledge of all nodes of graph.
I think that there are two solutions to make the shortest path.
Solution No1: http://postimg.org/image/sok88bsgd/
When user creates the floor map should make simultaneously the graph of this map. In other words user should make all of possible path in this map. The advantage of this solution is that the calculation of the shortest path is very fast but the disadvantage is that the creator should make all the possible path with his hand.
Solution No2: http://postimg.org/image/4c2bd7smr/
The system calculate all of the SVG object and calculate the shortest path. The huge disadvantage of this solution is that the calculation is very very slow.
Do you have a better solution?
Thank you for your response.
Source: (StackOverflow)
i'm making a simple iPhone game using cocos2d-iphone. I have an array of fiends, the "fiendSet" which has to navigate around a field full of obstacles. I spent the last three nights trying to get my A* pathfinding to work. I found the actual A* implementation here on stackoverflow and it works brilliantly. However, once i try to move my fiends around i run into trouble.
Each of my fiends has a CGPoint called motionTarget which contains the x and y values for where the fiend has to go. If only set the positions x and y to absolute values once a second, it works, like so:
-(void) updateFiendPositions:(ccTime)dt {
for (MSWFiend *currFiend in fiendSet) {
currFiend.position = ccp(currFiend.motionTarget.x,currFiend.motionTarget.y);
}
}
However, this doesn't look very nice, the fiends just "jump" 20px each second instead of animating nicely. I only implemented this as a placeholder method to verify the pathfinding. Now i want smooth animation. This is what i did:
-(void) updatePositions:(ccTime) dt {
for (MSWFiend *currFiend in fiendSet) {
if (currFiend.motionTarget.x != -1 && currFiend.motionTarget.y != -1) {
float x,y;
if ((int)floor(currFiend.position.x) < (int)floor(currFiend.motionTarget.x)) {
x = currFiend.position.x+(currFiend.speed*dt);
}
if ((int)floor(currFiend.position.x) > (int)floor(currFiend.motionTarget.x)) {
x = currFiend.position.x-(currFiend.speed*dt);
}
if (abs((int)floor(currFiend.position.x)-(int)floor(currFiend.motionTarget.x)) < 2) {
x = currFiend.motionTarget.x;
}
if ((int)floor(currFiend.position.y) < (int)floor(currFiend.motionTarget.y)) {
y = currFiend.position.y+(currFiend.speed*dt);
}
if ((int)floor(currFiend.position.y) > (int)floor(currFiend.motionTarget.y)) {
y = currFiend.position.y-(currFiend.speed*dt);
}
if (abs((int)floor(currFiend.position.y)-(int)floor(currFiend.motionTarget.y)) < 2) {
y = currFiend.motionTarget.y;
}
currFiend.position = ccp(x,y);
}
}
}
This works great for fiends moving in one direction. As soon as a fiend is supposed to go around a bend, trouble starts. Instead of for example first going up, then right, then down; my fiends will combine the up/right motion into one, they are "cutting corners". I only want my fiends to move either north/south OR east/west for each position update, not both. In other words, i don't want to animate changes to x and y simultaneously. I hope this explanation is clear enough..
I'm pretty sure i have a logic error somewhere.. i just havn't been able to figure it out for the last three sleepless nights after work.. Help!
Source: (StackOverflow)
I'm currently facing a problem with pathfinding on a map of tiles: I have an ArrayList<ArrayList<Byte>>, which determines if the tile at list.get(y).get(x) is blocked or not, and the starting position. Now I want to know if there is a path, starting at the origin, which goes over each non-blocked tile once, and if there is, I want the directions printed out, like 'NWWEW'. I already have got the part of checking if each non-blocked tile is connected to all others (thus, there should be only one area of connected non-blocked tiles) by using floodfill, but I still need an idea on how to go on with the 'path-but-each-tile-only-once'-thing.
If anyone has got any ideas or algorithms, I'd be thankful for answers
Edit: Alright, I think I've got it, but since the question was closed, I'll have to write the solution here:
(Thanks to @Jack for pointing me in the right direction) First of all, the program checks if the current tile is walkable; it'll then be marked as visited and the direction how it has been accessed is added to the directions-string. After that, I call this function recursively for each direction until the length of the total-directions-string is equal to the total number of accessible tiles on the whole map -1. If it's not equal, it removes the direction in which itself has been accessed and returns to the upper layer.
Code:
public static void findPath(int x, int y, String direction){
if(pathFound)
return;
if(map.get(y).get(x) == 0){
map.get(y).set(x, (byte) 1);
directions += direction;
findPath(x, y-1, "N");
findPath(x, y+1, "S");
findPath(x-1, y, "W");
findPath(x+1, y, "O");
if(directions.length() == totalFreeTiles-1){
pathFound = true;
return;
}
if(directions.length() > 0)
directions = directions.substring(0, directions.length()-1);
map.get(y).set(x, (byte) 0);
}
}
Source: (StackOverflow)
I have a little problem with theory so I hope that you guys will help me.
Imagine 2D game...You are some square and you have to go from start to finish. Between start and finish are some moving objects. They are moving vertically and horizontally with different speed from player and from each other. So, I need some algorithm for testing is there a chance for player to finish level, or is there some fault in level design. If you have more details please google "The Worlds Hardest Game", try that game and you will see what I need.
I think that I could use A* algorithm for finding path and somehow customize it for working with static and moving boundaries, but I dont know how and is it even possible.
Cheers :)
Source: (StackOverflow)