AI and Pathfinding

Retr0gamer

So I just had my first experience writing some really difficult coding algorithms. It's taken me 4 days to write a hex grid pathfinding routine but I think it's about finished now (barring any bugs that might still crop up). I couldn't find any code fragments similar to what I needed so had to code the whole thing from scratch in Lua (I'm using Corona). My heads absolutely melted at this stage

Anyway has anyone got any tips or links about pathfinding or writing AI because I don't want to have to go through that again of coding from scratch! Also when I go to design my own games it will be handy for making more interesting enemies and even for strategy games.

Genghiz Cohen

A* would be my first instinct for any kind of complex pathfinding. If it's for stupid simple drones then a line of sight/breadcrumb would do.

Retr0gamer

I only discovered A* after I started coding. It didn't really help but did put my mind at ease because I noticed I was actually coding something very similar to A* I noticed about he heuristics thing but as well but that wouldn't have worked for me and I've seen it fail a lot of times as well when things get complex.

gizmo

I'd highly recommend this book for the task Retr0. It deals with both the theory behind various techniques but also implements them in clear way via PyGame. The BookDepository have it for half the price Amazon are currently charging too.

As I mentioned in a thread over in the Games forum, this website is also a great resource for a whole host of AI articles, with some cracking ones based on actual real world implementations as seen in the likes of Halo, Fear etc...

oisincar

Well done on figuring out hex grid pathfinding I have no idea how even the coordanate system would work!

One series of videos that i found very interesting, if not useful to me just yet are the CS188 lectures from berkley. They're on youtube here: http://www.youtube.com/user/CS188Spring2013/videos?flow=grid&sort=da&view=0

They cover a* (Which they call "Informed search"), but they mainly focus on turn based games, expecially later on.

Heuristics tho will make your game run so much faster. The heuristics don't even have to be that accurate, they'll still help a huge amount. (As long as they're optimistic: they underestimate the tim it'll take to get to the goal.) Especially in larger searches, with few obstacles, heuristics will guide the nodes (the grid spaces) you explore towards your goal.

Hope this helps somewhat...
Oisin.

Retr0gamer

I choose not to use heuristics because I thought if the character didn't take the shortest path to the players choosen destination it would be frustrating for the player. Also it's only a small single screen 13x13 grid so it's not that intensive to work it out so the increase in speed really isn't needed.

The coordinate system isn't so bad. I used a reference system, instead of pixel coordinates I just numbered them. I have my level loading table set up so that I can plug them in like this: levelTable[x refernce][y reference] and there's an associative array in there with the pixel coordinates of that hex. One thing with hexes is that working out the six surrounding hexes is worked out differently depending on if the y reference is odd or even.

My algorithm is set up to build an array of all possible paths until it reaches an end point. If there's a split it copies that path into a new row in the table and changes the last reference to the new one. It also stops checking paths if they result in a dead end or backtrack over themselves. When it hits the endpoint it returns out a new table with the optimal path.

I found a really annoying Lua problem doing this as well since it uses tables instead of arrays. If you copy a row in a table to a new row both rows are somehow linked so if you change something in one it changes the other which resulted in a day of swearing and headbutting the table.

oisincar

Ah, ok that's interesting. So each hex has each own number, and then by knowing the row length you can work out it's adjacent hexes' numbers? nvm, i get it now. I'm guessing it works kind of like orthogonal coords, but every second row is shifted off half a space?

For 13 x 13 it's probably fine, especially seen as you're waiting for user input. A*'s more trouble than it's worth. I will say tho, as long as your heuristics are less than the actual cost, a* will always find the shortest path.

Your algorithm sounds a lot like bfs, or breadth first search, btw.

Oisin

Retr0gamer

Yeah it's kind of like that. The pixel coordinates were kind of a pain to work out but once I drew it out myself it made sense. Once I had that I just wrote an algorithm to work it out for the entire grid.

Well I got the animation and movement system working and tested it on the Corona simulator and it's pretty much instantaneous so no worries about lag between input and movement thank god, was worried about that.

It gives me a great appreciation of coders of yesteryear getting AI working in strategy games on much less powerful hardware. If you think about it stuff like Fire Emblem on the Famicom or Laser Squad on the ZX spectrum are carrying ou much more complex calculations than my code and are on dreadful hardware.