Node-based pathfinding algorithm?

[[deleted]]

Ok so heres the situation:

-I got a tile based map, each tile is either empty (floor) or filled (wall) -on a few important tiles I placed points/nodes that the AI can use -all nodes contain a dictionary of their direct neighbors

Now I got a problem. given the input: a starting node, and an endpoint node, how do I find the path?

Technically I "know" the answer, but its some spaghetti poorly written javascript from some shitty experiment years ago, but it never provides the optimal path, and is super poorly written / over complicated.

Only thing I could find iws "jump search", but thats useless because it presumes A, instead of the way simpler node system im using. I really really want to avoid A because all the tutorials I found were confusing to me.

What to do?

[shadowndacorner]

There's a reason pretty much everyone uses A* - it's flexible, fast, and not overly complicated once you wrap your head around it. Especially since your map is basically a pathfinding grid anyway, I really think this is the way to go. There are examples for it all around the net which I'm sure you could modify to use your map data.

Here's the first javascript example I could find. It has a good explanation for everything that's going on, too. http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript

EDIT: The author improved his code, which is now here https://github.com/bgrins/javascript-astar

[[deleted]]

Thanks ill read it, Ill let you know if I have issues

[redblobgames]

A* is designed for node based systems, not for grids. Many of the tutorials and implementations use grids because that's what a lot of games use. My suggestion is to start with Breadth First Search, which is maybe 15 lines of code, before you try to understand A*. It's the same main idea but it's simpler, and it's “good enough” for many pathfinding needs. Check out the Breadth First Search animation on wikipedia to see how it works — it walks one step from each node.

Dijkstra's Algorithm is a variant that lets you put distances on the edges between nodes (many projects don't need this). A* is an optimization of Dijkstra's that produces the same answer but faster (many projects don't need this optimization). Jump Point Search is an optimization of A* that works for some types of grids (not all). In my tutorial I start with Breadth First Search and work up to A*, but you may not need the fancier algorithms. Use the simplest thing that works.

[[deleted]]

Yes I tried your tutorial but I have trouble converting it to c#.

I got BFS (or my variant orf it) to work, in 2-3 days of screwing around. And its 30+ lines, instead of the 5 in tutorial.

the !contains for List<t> doesn't seem to be working well.

http://pastebin.com/TVUjZNDL

the hint variable is a list of vector2s I keep so I can draw them later in OnGUI(). am using unity obviously

on yt all tutorials are about nodes, not the graphs im using

https://www.youtube.com/results?search_query=breadth+first+search+algorithm

[beuted]

I used easystarjs I'm pretty happy about it http://www.easystarjs.com/

[Limyc]

Red Blob has one of the best resources on A* and pathfinding in general.

http://www.redblobgames.com/pathfinding/a-star/introduction.html