Извините, ничего не найдено.

mr.DIMAS · 12.11.2014, 15:28

В общем сделал поиск пути по Дейкстре - мне он показался проще для понимания.

Если кому нужен код - он ЗДЕСЬ
Написан на C++11, если кто будет компилировать\запускать, то результат смотреть через отладчик - ибо мне было лень делать вывод в консольку. В скором времени запилю его в игру.

pax · 12.11.2014, 19:38

AStar очень простой, и работает быстрее Дейкстры, т.к. имеет направление поиска (функцию эвристики). http://www.policyalmanac.org/games/a...torial_rus.htm

1) Добавляем стартовую клетку в открытый список.

2) Повторяем следующее:

a) Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой.

b) Помещаем ее в закрытый список. (И удаляем с открытого)

c) Для каждой из соседних 8-ми клеток ...

Если клетка непроходимая или она находится в закрытом списке, игнорируем ее. В противном случае делаем следующее.

Если клетка еще не в открытом списке, то добавляем ее туда. Делаем текущую клетку родительской для это клетки. Расчитываем стоимости F, G и H клетки.

Если клетка уже в открытом списке, то проверяем, не дешевле ли будет путь через эту клетку. Для сравнения используем стоимость G. Более низкая стоимость G указывает на то, что путь будет дешевле. Эсли это так, то меняем родителя клетки на текущую клетку и пересчитываем для нее стоимости G и F. Если вы сортируете открытый список по стоимости F, то вам надо отсортировать свесь список в соответствии с изменениями.

d) Останавливаемся если:

Добавили целевую клетку в открытый список, в этом случае путь найден.
Или открытый список пуст и мы не дошли до целевой клетки. В этом случае путь отсутствует.
3) Сохраняем путь. Двигаясь назад от целевой точки, проходя от каждой точки к ее родителю до тех пор, пока не дойдем до стартовой точки. Это и будет наш путь.

mr.DIMAS · 12.11.2014, 20:28

Код в студию. Именно код, где на вход дается граф, начало и конец а на выходе массив точек, представляющий путь из начала в конец.

Мне не нужна скорость( да и я чет сомневаюсь в особом приросте производительности, учитывая что процессоры сейчас намного мощнее ), у меня всего один враг. И еще граф у меня разреженный, не двумерный массив.

Кароч не вижу смысла переходить на A*, когда я уже прикрутил код, данный выше, к игре.

Mr_F_ · 12.11.2014, 21:15

A* это тот же Дейкстра, но быстрее (меньше проверяет)

Дейкстра:

А*

Прикладываю сорс либы, которую я юзал в своём эксперименте по поиску путей, на который потом забил.
То что нужно вроде в CalculateGlobalPath

cahekp · 12.11.2014, 21:23

Сообщение от tirarex

OpenAl.dll (или как его там) удали , мне помогало.

А мне не помогло.

При запуске говорит, что файл "OpenAL32.dll" не найден. Сайт openal.org выдает только короткое "coming (back) soon". Пришлось гуглить файл отдельно. Спустя минут 15 нашел нужный. Прикрепляю к посту на случай, если у кого возникнет такая же проблема, как у меня.

mr.DIMAS · 12.11.2014, 21:29

В следующем билде будет лежать установщик OpenAL'a.

pax · 12.11.2014, 22:36

Сообщение от mr.DIMAS

Код в студию. Именно код, где на вход дается граф, начало и конец а на выходе массив точек, представляющий путь из начала в конец.

Вообще писал так, чтобы можно было и другие алгоритмы поиска использовать, поэтому есть отдельно Waypoint (на карте) и AStarNode - содержит стоимость пути, эвристику и приоритет точки.



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

// класс вейпоинта
public class Waypoint
{
        public Vector3 position;
        public List<WayPointLink> nearPoints = new List<WayPointLink>(); // связи
        public int index; // индекс вейпоинта в массиве вейпоинтов
}

// связь с заранее посчитанным расстоянием до соседней точки
public class WayPointLink
{
        public Waypoint waypoint;
        public float distance;
}


public static class AStar
{
    // разные эвристики

    public static float DistanceHeuristic(Waypoint wp1, Waypoint wp2)
    {
        return (wp1.position - wp2.position).magnitude;
    }

    public static float Distance2DHeuristic(Waypoint wp1, Waypoint wp2)
    {
        var vec = wp1.position - wp2.position;
        var vec2 = new Vector2(vec.x, vec.z);
        return vec2.magnitude;
    }

    public static float SqrDistanceHeuristic(Waypoint wp1, Waypoint wp2)
    {
        return (wp1.position - wp2.position).sqrMagnitude;
    }

    public static float SqrDistance2DHeuristic(Waypoint wp1, Waypoint wp2)
    {
        var vec = wp1.position - wp2.position;
        var vec2 = new Vector2(vec.x, vec.z);
        return vec2.sqrMagnitude;
    }

    public static float SumHeuristic(Waypoint wp1, Waypoint wp2)
    {
        var vec = wp1.position - wp2.position;
        return Mathf.Abs(vec.x) + Mathf.Abs(vec.y) + Mathf.Abs(vec.z);
    }

    public static float Sum2DHeuristic(Waypoint wp1, Waypoint wp2)
    {
        var vec = wp1.position - wp2.position;
        return Mathf.Abs(vec.x) + Mathf.Abs(vec.z);
    }


    // собственно функция поиска, получает весь массив точек, начальную и конечную точки
    // возвращает путь
    public static List<Waypoint> FindRoute(List<Waypoint> waypoints, Waypoint start, Waypoint end,
        Func<Waypoint, Waypoint, float> heuristic = null)
    {
        if(heuristic == null)
        {
            heuristic = DistanceHeuristic;
        }

        // открытые поинты, сортированные по приоритету (с учетом пути и эвристики)
        var opendSet = new List<AStarNode>();
        // дополнительная коллекция для быстрого поиска 
        var opendSetById = new Dictionary<int, AStarNode>();

        // уже просмотренные точки
        var closedSet = new Dictionary<int, AStarNode>();

        // стартовая точка
        var startNode = new AStarNode(start);
        startNode.g = 0;
        startNode.h = heuristic(startNode.waypoint, end);
        startNode.f = startNode.g + startNode.h;

        // добавляем ее в список точек для просмотра 
        opendSet.Add(startNode);
        opendSetById.Add(startNode.waypoint.index, startNode);

        // пока есть точки в открытом списке выполняем поиск
        while (opendSet.Count > 0)
        {
            // достаем последнюю точку (ближайшую до целевой)
            var x = opendSet[opendSet.Count - 1];

            // если это конечная точка, то строим маршрут
            if (x.waypoint == end)
            {
                return ConstructRoute(x);
            }

            // переносим точку в список просмотренных
            opendSet.RemoveAt(opendSet.Count - 1);
            opendSetById.Remove(x.waypoint.index);
            closedSet.Add(x.waypoint.index, x);

            // просматриваем все точки, которые рядом с точкой, которую мы обрабатываем 
            foreach (var yWp in x.waypoint.nearPoints)
            {
                // если точка уже просмотрена, то пропускаем
                if (closedSet.ContainsKey(yWp.waypoint.index)) continue;

                // 
                var wp = waypoints[yWp.waypoint.index];
                AStarNode y;

                //расчетная стоимость пути до этой точки из обрабатываемой
                var tentativeGScore = x.g + yWp.distance;
                
                // необходимость изменить родителя просматриваемой соседней точки и пересчитать параметры, 
                // при условии что стоимость пути до нее меньше или при первом добавлении
                var tentativeIsBetter = false;

                // если точна не существует в открытом списке, создаем точку и добавляем в список открытых
                if (!opendSetById.ContainsKey(wp.index))
                {
                    y = new AStarNode(wp);
                    добавляем точку в сортированный список по дистанции
                    InsertSorted(opendSet, y);
                    opendSetById.Add(y.waypoint.index, y);
                    tentativeIsBetter = true;
                }
                else 
                {
                    // точка уже добавлена в открытый список
                    y = opendSetById[wp.index];
                    // если стоимость меньше, то меняем родительскую точку и пересчитываем параметры
                    if (tentativeGScore < y.g) 
                    {
                        tentativeIsBetter = true;
                    }
                }

                if (!tentativeIsBetter) continue;


                // обновление точки
                y.from = x;
                y.g = tentativeGScore; // стоимость пути
                y.h = heuristic(y.waypoint, end); // эвристика данной точки
                y.f = y.g + y.h; // приоритет 

                // сортировка массива по приоритету
                UpdateSorted(opendSet, y);
            }

        }
        return null;
    }

    // функция перемещает точку по массиву используя ее приоритет (не сортирует остальные точки)
    // писал давно, не помню точно как работает, но наиболее приортитетные точки в конце списка,
    // из конца дешевле убирать точки, не придется сдвигать весь массив
    private static void UpdateSorted(List<AStarNode> opendSet, AStarNode aStarNode)
    {
        var index = opendSet.IndexOf(aStarNode);
        if (index >= 0)
        {
            var isDown = false;
            for (int i = index + 1; i < opendSet.Count; ++i)
            {
                if (opendSet[i].f >= opendSet[i - 1].f)
                {
                    var temp = opendSet[i];
                    opendSet[i] = opendSet[i - 1];
                    opendSet[i - 1] = temp;
                    isDown = true;
                }
                else
                {
                    break;
                }
            }

            if (!isDown)
            {
                for (int i = index - 1; i > -1; --i)
                {
                    if (opendSet[i + 1].f < opendSet[i].f)
                    {
                        break;
                    }

                    var temp = opendSet[i];
                    opendSet[i] = opendSet[i + 1];
                    opendSet[i + 1] = temp;
                }
            }
        }
        else
        {
            // не существует элемента в списке
        }
    }

    // добавляет точку в массив открытых точек в позицию с учетом приоритета
    private static void InsertSorted(List<AStarNode> opendSet, AStarNode aStarNode)
    {
        for (int i = 0; i < opendSet.Count; ++i)
        {
            if (!(aStarNode.f < opendSet[i].f)) continue;

            opendSet.Insert(i, aStarNode);
            return;
        }

        opendSet.Add(aStarNode);
    }

    // функция строит путь
    private static List<Waypoint> ConstructRoute(AStarNode end)
    {
        var route = new List<Waypoint>();

        var wp = end;
        route.Add(wp.waypoint);
        while (wp.from != null && wp != wp.from)
        {
            wp = wp.from;
            route.Add(wp.waypoint);
        }
        if (route.Count>0)
            route.RemoveAt(route.Count-1);
        route.Reverse();

        return route;
    }

    public class AStarNode
    {
        public readonly Waypoint waypoint; // связь с точкой на карте
        public float g; // стоимость
        public float h; // эвристика
        public float f;  // приоритет

        public AStarNode from; // откуда в эту точку посчитана стоимость

        public AStarNode(Waypoint wp)
        {
            waypoint = wp;
        }
    }
}

mr.DIMAS · 20.11.2014, 19:01

Сделал стелс режим. На втором уровне теперь ходит главный злодей. Собственно протестируйте стелс режим и про баги расскажите.

Стелс-режим - [C]

Соответственно добавлен индикатор видимости, типа как в скайриме\обле.

Первая встреча с главным злодеем поможет вам построить кирпичный дом.

Есть один баг пока-что, злодей не сохраняется - то есть если загрузиться он будет в том же положении что и перед загрузкой. Это я поправлю когда сделаю ему нормальные мозги.
СКАЧАТЬ

St_AnGer · 20.11.2014, 20:09

Попробовал. Сразу - не подружился с камнем во втором уровне (на первом перекрёстке). Он выкинул меня за пределы уровня. Быть может, я его обидел, тем что хотел сдвинуть... А если на этом же перекрёстке пойти налево и перелезть через тележку так же улетишь с карты. И ещё, игрок съезжает с наклонных поверхностей (коэфициент трения низкий наверно).

mr.DIMAS · 20.11.2014, 22:06

Небольшой пачт, устраняет баги в поведении.

pax · 21.11.2014, 00:16

Поиграл первый раз. Появился в лесу, пошел в ту сторону, в которую изначально смотрел. Уперся в воздух. Увидел вверху красный текст. Попробовал посмотреть по сторонам. Пошел в другую сторону, шел долго, потом понял что можно бегать. При беге сильно неестественно камера меняет перспективу имхо. Забежал в шахту, сзади что-то обвалилось, загрузился наверное второй уровень. Иду вперед, на столе что-то слишком белое для темного туннеля, записку не прочитал, что-то взял со стола и пошел дальше. Меня убивает какой-то черт. Красный экран, сверху надпись говорит что надо найти друзей. Но я мертвый, не могу их искать дальше и камера постоянно крутится. Не понял как начать сначала, можно только продолжить смотреть на свою смерть...

mr.DIMAS · 21.11.2014, 00:19

Загрузка\сохранение тебе в помощь. F5\F9 по умолчанию.

pax · 21.11.2014, 00:20

В меню не нашел...

mr.DIMAS · 21.11.2014, 08:07

Ок. Сделаю отдельные пункты в меню. И сохранение в разные слоты. Со второго уровня игру придется проходить аккуратно, иначе будут постоянно убивать.

mr.DIMAS · 22.11.2014, 20:15

Если кто помнит, у меня с новым булетом были проблемы - персонаж постоянно "дрожал", была в общем ебала с физикой. Так вот виновата была автоматическая оптимизация с SSE. Новый булет компилится с ключами /arch:SSE2 или /arch:SSE. Стоило выключить SSE, все стало чудесно - никакой тряски и прочей дури. В то же время в новом булете есть ручная оптимизиция с SSE, так что скорость работы осталась прежней. Если чо, компилятор от 2012 студии с Update 1. Видимо это platform-specific bug какой-то. Гугление ни к чему не привело. Подсказал про это Samodelkin, за что ему спасибо.