In my game I want to spawn a monster which would immediately calculate a path to its target. If the monster faces any new obstacles, he destroys it and goes further on the calculated way. If there is no path to the target (the way is fully blocked) he destroys everything and goes straight to the target. The target is this Yellow cube. Maze is made from black cubes. And available path is in white. The monster can't go crosswise.

The total area width and height can be different. Here now is 12x14.

Could you help me please with formula? Given maze_width + maze_height + starting_point + target_point + all area black cubes x/y coordinates.

This is too complex for my non-mathematical head and I really want to implement this pathfinding formula in my game :)

So I need only one formula for the first once-made pathfinding, nothing more. I will use it with JavaScript.

Thanks in advance for any help!

const MAZE_WIDTH = 12;
const MAZE_HEIGHT = 14;
const STARTING_POINT = [0, 1];
const TARGET_POINT = [6, 6];

function get_path(maze_blocks) {

var maze_blocks = [[2, 1], [8, 1], [1, 7] ... ]; // not sorted
get_path(maze_blocks) // returns [[0, 1], [1, 1], [1, 2], [1, 3] ...]

enter image description here

  • 6
    \$\begingroup\$ Did you look into something like A*? \$\endgroup\$ – Vaillancourt May 2 '17 at 10:12
  • \$\begingroup\$ We don't support questions asking for technology to use,vplease refer to our help center \$\endgroup\$ – Bálint May 2 '17 at 10:39
  • \$\begingroup\$ It is not an ask for technology to use. why did you think that?? I am asking for help with formula. \$\endgroup\$ – mansim May 2 '17 at 12:30
  • 1
    \$\begingroup\$ Dijkstra's algorithm is even a step simpler than A*. \$\endgroup\$ – Philipp May 2 '17 at 22:18
  • 1
    \$\begingroup\$ @Philipp in the absence of different edge costs, you could go a step simpler still and just run breadth-first search to get the same results as Dijkstra's. ;) \$\endgroup\$ – DMGregory May 3 '17 at 11:59

Usually A* is the choosen algorithm for pathfinding in videogames since it's easy to implement and yields a decent behaivour but in your case i think it's not necesary.

If you dissects your needs, you can realize that what you really want is to check the relative position of the target from the enemy, once you have this vector, since your enemy can break walls, you only have to break and advance in that direction.

Moving just toward the player's direction would be weird, so you can use a flood aproach to check what's the closest accessible tile to the player by checking the distance between both entities and move the enemy there. once you get the closest cell you can go, then you break and repeat.

EDIT: You asked for a formula but it's not that easy, we are here to help and support you, not to spoon-feed you. Is your task now to get the answers, learn some maths and implement your code understanding what you'r doing.

Keep trying mate :)

  • \$\begingroup\$ Hello. Thanks for answer. My enemy can break walls only if there is a closed path. I looked at A*, and Dijkstra. And this flood aproach. So far seems A* is ok, still looking maybe exist something with less iterations. \$\endgroup\$ – mansim May 4 '17 at 11:38
  • \$\begingroup\$ @mansim The "*" in "A*" means "provably optimal". For a given heuristic, you can't iterate through fewer cells than A* does for a single path. Improvements to A* are mostly about using better heuristics or re-using pieces of path unchanged from a previous result. \$\endgroup\$ – DMGregory Nov 11 '20 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.