So in my third year, we're doing a module on AI. Not the neural network kind, the in game bot behaviour kind.
Anyways I've been looking for an excuse to do some graphics programming and we're looking at pathfinding last week. And I got inspired yay.
Everyone knows A* is one of the best pathfinding algorithms and I should probably just implement a version of it but I got inspired to try something different.
Usually with pathfinding algorithms we have for loops and while loops using iterators as IDs for objects. This just looks like the perfect opportunity to try make some parallel computing in the ol' graphics card.
I've looked at other peoples compute shaders for pathfinding and some of them are still iterative. Which is wrong. You want to avoid iterative stuff when working in parallel surely. So mine will be... iterative as well because it makes sense.
Straight to my my idea:
Each node has a desirability and lower means good. Higher means bad.
There's a start position, an end position and a bunch of nodes in between and all around.
First challenge is how to calculate desirability of these nodes in parallel.
Easiest way to calculate desire would be distance to the target node. This means that after the nodes have been calculated, we just need to look for the closest adjacent node with the lowest score to get closer to our target.
But then obstructions become a problem. A wall or pitfall doesn't look like a problem when you're only using distance to a target.
This is where I thought the direction to the node would also be desirable. So friendly old dot product comes in and here's the simplified result:
Node Desire = The percentage of the distance left to cover to the target multiplied by the desired direction to the target.
Maybe you're wondering, why use the desired direction and dot product and it seems useless in this current context?
That's because the next part isn't made yet. I'll get on to that step in a moment.
These nodes are generated randomly and unlinked which is useless now that I've proven some weighing can be done in parallel. Because now I need the nodes to look at adjacent nodes that they are connected to.
For each node, we'll look at the adjacent nodes score and add it to the current nodes score.
Say that one nodes direction is not towards the target, it will be undesirable and we want that to affect the score of the node it's attached to. It's difficult to explain without a working solution.
Anyways I need to create a Navmesh and using the old techniques of indexed based drawing in an unusual way, we should get it working..
What's special about this idea is that without reinitialising the nodes scores, repeating the dispatch of the compute shader will make the scores more accurate and increase the foresight of each node.
No idea if any of this will work but I've already proven half of it and it's been easier than I expected. May as well keep going.
Comentários