Closest object to a goal?

NolanCYT · September 13, 2023, 9:14pm

I’m remaking a tile-based movement dungeon game like Pokémon Mystery Dungeon, or Pixel Dungeon. (I’m only remaking the dungeon part.)
And I need to figure out how to get all active enemies to go toward the player. My initial thought was because I’m using part that exist in the workspace as a grid for the player to move, I could utilize those same tiles for the enemy’s movement.

So how would I go about getting the closest tile to the enemy that is closest to the player (if that all makes sense)?

azqjanna · September 13, 2023, 9:28pm

Easy option: Assume the tile thats in the direction of the player is always the right way, accepting some enemies getting stuck if the player runs around a wall.

Hard option: Implement Djikstra, or find one that you can make work with your map (probably out there somewhere)

NolanCYT · September 13, 2023, 9:30pm

My apologies for asking, but what exactly is Dijkstra? Is it like a path-finding algorithm?

azqjanna · September 13, 2023, 9:33pm

Djikstra finds the shortest path through a Graph. A grid is a special case where each edge of the graph costs about the same.
Dijkstras_progress_animation

NolanCYT · September 13, 2023, 9:38pm

I think I’d like to do that as I want to this to function close to perfectly. Can you refer me to any open source script or anything to help me go about implementing this into my game?

azqjanna · September 13, 2023, 9:44pm

github.com

kennyledet/Algorithm-Implementations/blob/master/Dijkstra's_Shortest_Path/Lua/Yonaba/dijkstra.lua

-- Generic Dijkstra graph search algorithm implementation
-- See : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

-- Notes : this is a generic implementation of Dijkstra graph search algorithm.
-- It is devised to be used on any type of graph (point-graph, tile-graph,
-- or whatever. It expects to be initialized with a handler, which acts as
-- an interface between the search algorithm and the search space.

-- This implementation uses internally a binary heap to handle fast retrieval
-- of the lowest-cost node.

-- The Dijkstra class expects a handler to be initialized. Roughly said, the handler
-- is an interface between your search space and the generic search algorithm.
-- This model ensures flexibility, so that this generic implementation can be 
-- adapted to search on any kind of space.
-- The passed-in handler should implement those functions.
-- handler.getNode(...)    -> returns a Node (instance of node.lua)
-- handler.getAllNodes()   -> returns an array list of all nodes in graph
-- handler.distance(a, b)  -> heuristic function which returns the distance
--                            between node a and node b

This file has been truncated. show original

If you use this you will need the other files it refers to, and have to change the require() calls to use Roblox paths.