Pathfinding and A*

If I want my NPCs to move towards the player on a nxm grid, and the grid can contain trees that the NPC cannot pass, I need an algorithm that finds the shortest path to the player.

I gave this as a problem to ChatGPT:

In class level I would like to have a new method shortestPath that finds out the shortest path that an NPC on coordinate startX, startY has to take to reach coordinate endX, endY, avoiding any squares where the top levelObject cannot be traversed. The result should be a list of coordinates starting with startX, startY and ending with endX, endY where each coordinate can be reached horizontally, vertically or diagonally from the previous one.

To which it responded with:

This sounds like a pathfinding problem, which can be solved using various algorithms such as A*, Dijkstra's Algorithm, or Breadth-First Search. Since you want to allow diagonal movement as well, A* would be a good choice here. However, please note that implementing such algorithms in a complex environment can be quite challenging.

Here's a simplified example of how you might implement an A* algorithm in your Level class. This code is for educational purposes and may need to be adjusted to fit your actual game structure and requirements:

<plus code that looked like a decent implementation of A* for my purposes>

Okay, back then, 30 years ago, I learned about A*, even implemented a chess engine with A* that mysteriously didn't perform anywhere as good as alpha-beta :-). I'm impressed that ChatGPT didn't try to come up with a hacked solution on its own, but knows the relevant algorithms and is able to adapt them to my situation (it was using the right methods to access information that A* needs, eg to create and update candidates).

But situations like this one will be a problem for the (if I trust mastodon: many) people without development experience; A* isn't easy to grasp without a good explanation, and the code it generated is long and complex. This might be the situation when people hand over control to the bot because they are overwhelmed with the situation. And given my experience with ChatGPT, it can sometimes run into situation where it also doesn't understand its code anymore.

And if you don't have control, and ChatGPT doesn't have control then nobody has control over the code. 

(and then it's time to give up or ask an actual developer for help :-) )

Anyway, I was not yet in the mood to add A* to my code so I just made it possible to walk over trees and added pathfinding to my little backlog :-) - I'm much more eager to get the game into a state where I as the player can interact with ChatGPT and find out what it does if e.g. its first NPC offers me a weapon that I then use to attack it, and then approach the next NPC...