I'm developing game like Hitman Go , and I need to find which waypoints are closest to my target(specific waypoint ) when enemy has alerted by rock or sound and etc.

I set some point for enemy and My enemy patrolling between waypoints ( 8 -> 6 -> 1-> 2-> 3-> 4-> 5 ) then reveres his path. so, when I throw rock in waypoint number 18, I need to move enemy to this waypoint, but with closest way. imaging enemy can be any this waypoint when he get aleret ( 8,6,1,2,3,4,5 points).

Note 1: The distance between two points is same.

Note2: My game is in 3d not 2d.

I use this code to move my enemy step by step ( turn base ).

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class WaypointController : MonoBehaviour
{
    public List<Transform> waypoints = new List<Transform>();
    private Transform targetWaypoint;
    private int targetWaypointIndex = 0;
    private float minDistance = 0.1f;
    private int lastWaypointIndex;

    public bool reversePath;

    // what easetype to use for iTweening
    public iTween.EaseType easeType = iTween.EaseType.easeInOutExpo;

    // how fast we move
    public float moveSpeed = 1.5f;

    // time to rotate to face destination
    public float rotateTime = 0.5f;

    // delay to use before any call to iTween
    public float iTweenDelay = 0f;

    // Use this for initialization
    void Start()
    {
        lastWaypointIndex = waypoints.Count - 1;
        targetWaypoint = waypoints[targetWaypointIndex];
    }

    public void EnemyTurn()
    {
        float distance = Vector3.Distance(transform.position, targetWaypoint.position);
        CheckDistanceToWaypoint(distance);

        // move toward the destinationPos using the easeType and moveSpeed variables
        iTween.MoveTo(gameObject, iTween.Hash(
            "x", targetWaypoint.position.x,
            "y", targetWaypoint.position.y,
            "z", targetWaypoint.position.z,
            "delay", iTweenDelay,
            "easetype", easeType,
            "speed", moveSpeed
        ));
    }

    void CheckDistanceToWaypoint(float currentDistance)
    {
        if (currentDistance <= minDistance)
        {
            targetWaypointIndex  ;
            UpdateTargetWaypoint();
        }
    }

    void UpdateTargetWaypoint()
    {
        if (targetWaypointIndex > lastWaypointIndex)
        {
            if (reversePath)
            {
                waypoints.Reverse();
            }
        
            targetWaypointIndex = 1;
        }
        targetWaypoint = waypoints[targetWaypointIndex];
    }
}

CodePudding user response：

Since you asked in the comments for a non-A* solution & I was bored :)

Naive DFS pathfinder with very simple pruning. Brute force and very wasteful both memory & CPU wise.

For a game similar to Hitman Go / Lara Croft Go - I would use this code and not a navmesh / A*.

For a RTS / FPS or any AI intensive games, I would definitely not use this solution.

public class GridPathfinder
{
    // Not thread safe
    private int? _currentShortestPath;

    /// <summary>
    /// Finds shortest path from cell A to B
    /// </summary>
    /// <returns>Shortest found path; null if found no path.</returns>
    public IList<Node> GetShortestPath(Node a, Node b)
    {
        _currentShortestPath = null;
        return GetShortestPathInternal(a, b, new List<Node>());
    }

    private IList<Node> GetShortestPathInternal(Node @from, Node to, List<Node> currentPath)
    {
        // Sanity
        if (currentPath.Contains(from))
        {
            return null;
        }

        // Prune
        if (_currentShortestPath.HasValue && currentPath.Count   1 >= _currentShortestPath)
        {
            return null;
        }

        currentPath.Add(from);
        if (from == to)
        {
            return currentPath;
        }

        // Check neighbors recursively
        IList<Node> foundShortestPath = null;
        foreach (var connectedCell in from.ConnectedCells)
        {
            var cellPath = GetShortestPathInternal(connectedCell, to, new List<Node>(currentPath));
            if (cellPath == null || foundShortestPath != null && cellPath.Count >= foundShortestPath.Count)
            {
                continue;
            }

            foundShortestPath = cellPath;
        }

        // Update shortest path for future pruning
        if (foundShortestPath != null && (!_currentShortestPath.HasValue || _currentShortestPath > foundShortestPath.Count))
        {
            _currentShortestPath = foundShortestPath.Count;
        }
        
        return foundShortestPath;
    }
}

public class Node
{
    private readonly HashSet<Node> _connectedCells = new HashSet<Node>();

    public IEnumerable<Node> ConnectedCells => _connectedCells;

    /// <summary>
    /// Add a connection
    /// </summary>
    /// <param name="toAdd">Node to add</param>
    /// <param name="isTwoWay">Should add a connection from target node to this node</param>
    public void AddConnection(Node toAdd, bool isTwoWay=true)
    {
        if (toAdd == null || toAdd == this)
        {
            throw new Exception("Invalid connection attempted");
        }

        // Attempt to add
        if (!_connectedCells.Add(toAdd))
        {
            return;
        }

        if (!isTwoWay) return;
        toAdd.AddConnection(this);
    }
}