koobas.hobune.stream
Beginner needs help with Pathfinding
Ok, what I have currently is a "Chess Board" type level, in which I can click each tile of the board to move my character. This all works fine. What I now need is some sort of path finding so that my character moves from tile to tile, rather than just making a straight line through everything to where I've asked it to move.
To better explain, imagine you've just started a game of Chess. You can't move your knight, because a pawn stands in front of it. The problem I have is that if I select my knight, and attempt to move, my knight would just pass right through my pawn to wherever I've clicked. (I'm not making Chess this is just the best example I could think of to explain my problem without taking video)
My board has other "cubes" in the middle, but instead of going around them, my character clips right through them.
[x, x, x, x, x, x, x]
[x, x, x, x, x, x, x]
[x, o, o, \/, x, x, x]
[x, o, [], [], [], x, x]
[x, o, o, (), x, x, x]
[x, x, x, x, x, x, x]
[x, x, x, x, x, x, x]
Rather than the array's path below. (The o's represent the path taken, () represents my character, and the []s represent an obstacle in the way)
[x, x, x, x, x, x, x]
[x, x, x, x, x, x, x]
[x, x, x, \/, x, x, x]
[x, x, [], [o], [], x, x]
[x, x, x, (), x, x, x]
[x, x, x, x, x, x, x]
[x, x, x, x, x, x, x]
I've taken a brief look at a tutorial on UnityGems I saw recommended to another user on A*, but as a beginner I found the tutorial out of my depth, or at least now explained in a way a beginner would understand. Does anyone know of a tutorial, or a something along the same lines, that could be helpful to me in my goal?
One of the most optimal general path finding search is A star, without a doubt. If you're just a beginner at programming, creating your own implementation of A star is going to be tricky, because it requires knowledge of graphs and graph theory, priority queues, etc.
I suggest you find a solution that's already created. Unity Pro has a pathfinding solution with NavMesh, and there are plenty of pathing plugins on the Asset Store, some are quite cheap (Simply A* - $10).
Though, if you really want to implement A* yourself (or have no choice), I suggest you read up on the following topics (roughly in this order, give or take):
graph data structures, what types there are(acyclic graphs, etc.), and how they can be constructed (adjacency lists, etc.)
graph edges and what types there are (weighted, directed, undirected, etc.).
common graph traversals (depth-first search, breadth-first search)
min heaps, and how you can make priority queues with them (C# does not come with a standard one)
Dijkstra's algorithm: how it works (its a modified breadth-first search!)
heuristics: what they are and some common ones for A* (Eudlidean, Diagonal Shortcut, Manhattan Distance, etc.)
A* algorithm: how it works (its a modified Dijkstra!)
So you're saying that I basically need to understand each of these topics beforehand if I wish to use/implement A* into my game?
I'll take a look at the plugins on the Asset Store, but it seems as if these things might not do exactly what I would like them to, even if they could partially simulate what I wanted, I wouldn't understand the bare basic concepts to alter it to work how I want it to leaving me back at square one. Though I guess I should research the plugin's capabilities before ruling it out. I'll take a look!
Also, sadly I do not have Unity Pro so the Nav$$anonymous$$esh usage is out of my grasp.
you need to have some understanding of them and how they all work together to make A* possible, if you intend on implementing it.
I mean, a architect needs to know a little something about physics if he plans on building a stable bridge, right?
I edited my answer so there's less scary bullet points, btw.
Indeed I'd hope that architect did know a bit about physics eh?
Lol, that is much less scary. Also after brief research I've found it seems much easier to understand all these concepts than it is to understand how to implement them into script, but I guess that's what learning is for.
I'd recommend starting here - http://www.policyalmanac.org/games/aStarTutorial.htm
A* is pretty much the gold standard in pathfinding for games today and you should really understand the idea behind it before going further. When I first tried coding pathfinding I used this tutorial and I found it explained everything far and away better than any of the other tutorials I looked at. Once you have an idea of how to implement this in a general sense, you can probably either follow the unitygems tutorial, or implement it in your own way. Apart from this, you could take a look at using navmeshes and such, which I think is a unity pro option only and may not really solve your particular issue.
I'll take a look man, thanks. It sounds almost exactly like what I need.
