精华内容
下载资源
问答
  • 常用游戏算法
    千次阅读
    2021-11-09 11:02:31

     排序算法

     

    1.A*算法

     算法核心思想:

    2.递归算法

     例如AB包的依赖加载使用递归,程序是从最外层引用发起的,但第一个加载的居然是最内层的依赖AB包,递归真的妙!

    一般来说多次套娃的数据类型可以且适合用递归。

    3.洗牌算法Shuffle

    static void Shuffle(int[] arr)
    {
        Random r = new Random();
        int index;
        int temp;
        for (int i = 0; i < arr.Length; i++)
        {
            index = r.Next(arr.Length);    
            temp = arr[i];  //当前元素和随机元素交换位置
            arr[i] = arr[index];
            arr[index] = temp;
        }         
    }

     第二种取随机数的方式,从网上看到的

        void Shuffle(int[] arr)
        {
            int index;
            int cache;
            if (arr == null || arr.Length == 0)
                return;
            for (int i = 0; i < arr.Length; i++)
            {
                // 随机数是为了取余
                index = i + new System.Random().Next(0, 10000000) % (arr.Length - i);
    
                cache = arr[i];
                arr[i] = arr[index];
                arr[index] = cache;
            }
        }

     

    更多相关内容
  • leetcode刷题算法总结 AlgorithmTraining 算法训练,包括《啊哈算法》中的算法和常用游戏算法。 目录
  • 主要介绍了JS/HTML5游戏常用算法之追踪算法,结合吃豆人游戏算法原理以实例形式详细分析了追踪算法的相关算法操作技巧与注意事项,需要的朋友可以参考下
  • 主要介绍了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法,结合实例形式详细分析了针对迷宫游戏路径搜索算法的普里姆算法相关原理、实现方法及操作注意事项,需要的朋友可以参考下
  • 本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 像素检测算法。分享给大家供大家参考,具体如下: 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下。除非是在极为特殊的...
  • 【H5JS】游戏常用算法-路径搜索算法-随机迷宫算法(普里姆算法).pdf
  • 游戏中的算法

    千次阅读 2020-08-16 21:00:18
    游戏中的两个常用算法A*算法的介绍代码实现排序算法的应用 A*算法的介绍 游戏中的寻路通常由深度优先搜索(DFS)、广度优先搜索(BFS)或者A算法实现。其中DFS与BFS属于状态式搜索,A算法属于启发式搜索。今天给大家介绍...

    游戏中的两个常用算法

    A*算法的介绍

    游戏中的寻路通常由深度优先搜索(DFS)、广度优先搜索(BFS)或者A算法实现。其中DFS与BFS属于状态式搜索,A算法属于启发式搜索。今天给大家介绍一下A*算法。

    1. G(n)、H(n)、F(n)
      G(n)代表从起点到达节点n的实际代价值
      H(n)代表从节点n到达终点的估计代价值
      F(n)代表从起点经由节点n到达终点的估计代价值

      下面通过一个例子来计算 G(n)、H(n)、F(n)
      绿色方块为起点,蓝色为障碍,红色代表终点
      G(n)、H(n)、F(n)的计算

    2. G(n)、H(n)、F(n)的计算(以起点右边F=40的方块为例)
      G=当前格的G值 + 父节点(上一格)的G值
      直接将起点的右边这个方块称为当前格了。
      当前格的G值=10+0。
      这个10是当前格与父节点之间的代价,如果当前格在上一格的正方向,则代价为10,如果在上一格的斜方向则代价为14,可以对比当前这一格和当前上方的一格。然后要用这个代价加上父节点的代价,由于父节点是起点,所以父节点的G=0。

      H=(当前格与终点之间x方向的单位差 + y方向的单位差)*10
      当前格的H=(3+0)*10
      当前格与终点在x方向上差了三个单位,y方向差了0个单位

      F=当前格的G值+H值
      当前格F=10+30

    3.开启列表与关闭列表
    两个用来存储节点的容器,因为有很多的增删操作,所以选择List是比较好的。开启列表中存储的是可以行走的节点,关闭列表存储走过的节点,我们会在开启列表中选择一个F最小的值去走,那就要把这个点从开启列表中移除并加入关闭列表。

    4.流程
    1.将起点放入开启列表中
    2.while(开启列表不为空)
    {
    1.在开启列表中找到F值最低的点,称为当前格
    2.将当前格加入到关闭列表中,从开启列表移除
    3.遍历当前格的周围8个点
    if(不能走 || 在关闭列表中)
    continue;
    if(在开启列表中)
    当前的G值比较原来的G值,如果小于,更新GF值,更新父节点为当前格
    else
    将点放入到开启列表中,计算GHF值,设置父节点为当前格
    判断终点是否在关闭列表中,如果在,推导路径
    }

    代码实现

    #include <vector>
    #include <list>
     
    const int kCost1 = 10; //直移一格消耗
    const int kCost2 = 14; //斜移一格消耗
     
    struct Point
    {
        int x, y; //点坐标,x代表横排,y代表竖列
        int F, G, H; //F=G+H
        Point* parent; //当前点的父节点,用于回溯查找路径
        
        Point(int x, int y)
        :x(x),
         y(y),
         F(0),
         G(0),
         H(0),
         parent(NULL)  //带参构造
        {
        }
    };
    //A*算法
    class Astar
    {
    public:
        //初始化A*算法使用的地图
        void InitAstar(std::vector<std::vector<int>> &_maze);
        //获取路径:1.开始点 2.结束点 3.斜边移动是否考虑四周有障碍物
        std::list<Point*> GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);
    private:
        //查找路径的方法:A*算法的核心逻辑
        Point *findPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);
        //获取周围八个点,如果能走或者不在关闭列表中,则放入vector并返回
        std::vector<Point *> getSurroundPoints(const Point *point, bool isIgnoreCorner) const;
        //判断某个点是否可走
        bool isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const;
        //判断开启/关闭列表中是否包含某点
        Point *isInList(const std::list<Point *> &list, const Point *point) const;
        //从开启列表中查找F值最小的节点
        Point *getLeastFpoint();
        //计算FGH值
        int calcG(Point *temp_start, Point *point);
        int calcH(Point *point, Point *end);
        int calcF(Point *point);
    private:
        std::vector<std::vector<int>> maze;//地图(maze:迷宫)
        std::list<Point *> openList;  //开启列表
        std::list<Point *> closeList; //关闭列表
    
    };
    
    #include <math.h>
    #include "Astar.h"
     
    void Astar::InitAstar(std::vector<std::vector<int>> &_maze)
    {
        maze = _maze;
    }
     
    int Astar::calcG(Point *temp_start, Point *point)
    {
        //如果是斜边,extraG为14,否则为10
        int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? kCost1 : kCost2;
        //如果是初始节点,则其父节点是空
        int parentG = point->parent == NULL ? 0 : point->parent->G;
        //当前点的G值 = 父节点的G值 + 额外的G值
        return parentG + extraG;
    }
     
    int Astar::calcH(Point *point, Point *end)
    {
        //欧几里距离:两点之间的直线距离
        //return sqrt((double)(end->x - point->x)*(double)(end->x - point->x) + (double)(end->y - point->y)*(double)(end->y - point->y))*kCost1;
        //曼哈顿距离:水平距离+垂直距离
        return (abs(end->x - point->x) + abs(end->y - point->y)) * kCost1;
    }
     
    int Astar::calcF(Point *point)
    {
        //F = G + H
        return point->G + point->H;
    }
     
    Point* Astar::getLeastFpoint()
    {
        //将第一个点作为F值最小的点,进行比较,最终拿到F值最小的点
        if (!openList.empty())
        {
            auto resPoint = openList.front();
            for (auto &point : openList)
            if (point->F<resPoint->F)
                resPoint = point;
            return resPoint;
        }
        return NULL;
    }
     
    Point* Astar::findPath(Point& startPoint, Point& endPoint, bool isIgnoreCorner)
    {
        //把起始点添加到开启列表
        openList.push_back(new Point(startPoint.x, startPoint.y));
        do
        {
            auto curPoint = getLeastFpoint();//找到F值最小的点
            openList.remove(curPoint); //从开启列表中删除
            closeList.push_back(curPoint);//放到关闭列表
            //找到当前周围八个格中可以通过的格子(1.可走且没有在关闭列表)
            std::vector<Point*> surroundPoints = getSurroundPoints(curPoint, isIgnoreCorner);
            for (auto &target : surroundPoints)
            {
                //对某一个格子,如果它不在开启列表中,加入到开启列表,设置当前格为其父节点,计算F G H
                if (!isInList(openList, target))
                {
                    target->parent = curPoint;
     
                    target->G = calcG(curPoint, target);
                    target->H = calcH(target, &endPoint);
                    target->F = calcF(target);
     
                    openList.push_back(target);//添加到开启列表中
                }
                //对某一个格子,它在开启列表中,计算G值, 如果比原来的大, 就什么都不做,否则设置它的父节点为当前点,并更新G和F
                else
                {
                    int tempG = calcG(curPoint, target);
                    if (tempG < target->G)
                    {
                        target->parent = curPoint;
     
                        target->G = tempG;
                        target->F = calcF(target);
                    }
                }
                //查找结束点是否已经在开启列表中,如果在,这时候路径被找到。
                Point *resPoint = isInList(openList, &endPoint);
                //如果返回不为空,表示找到终点,则通过终点的parent一直反推得出路径
                if (resPoint)
                    return resPoint;
            }
        }while (!openList.empty());//当开启列表为空时,跳出循环
     
        return NULL;//找不到一条路径
    }
     
    std::list<Point*> Astar::GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner)
    {
        Point *result = findPath(startPoint, endPoint, isIgnoreCorner);
        std::list<Point *> path;
        //返回路径,如果没找到路径,返回空链表
        while (result)
        {
            path.push_front(result);
            result = result->parent;//通过parent回溯
        }
     
        //清空临时开闭列表,防止重复执行GetPath导致结果异常
        openList.clear();
        closeList.clear();
     
        return path;
    }
     
    Point* Astar::isInList(const std::list<Point *> &list, const Point *point) const
    {
        //判断某个节点是否在列表中,这里不能比较指针,因为每次加入列表是新开辟的节点,只能比较坐标
        for (auto p : list)
        if (p->x == point->x&&p->y == point->y)
            return p;
        return NULL;
    }
     
    bool Astar::isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const
    {
        //如果点与当前节点重合、超出地图、是障碍物、或者在关闭列表中,返回false
        if (target->x<0 || target->x>maze.size() - 1
            || target->y<0 || target->y>maze[0].size() - 1
            || maze[target->x][target->y] == 1
            || (target->x == point->x&&target->y == point->y)
            || isInList(closeList, target))
        {
            return false;
        }
        else
        {
            if (abs(point->x - target->x) + abs(point->y - target->y) == 1)//非斜角可以
                return true;
            else
            {
                //斜对角要判断是否绊住
                if (maze[point->x][target->y] == 0 && maze[target->x][point->y] == 0)
                    return true;
                else
                    return isIgnoreCorner;
            }
        }
    }
     
    std::vector<Point *> Astar::getSurroundPoints(const Point *point, bool isIgnoreCorner) const
    {
        std::vector<Point *> surroundPoints;
     
        for (int x = point->x - 1; x <= point->x + 1; x++)
        for (int y = point->y - 1; y <= point->y + 1; y++)
        if (isCanreach(point, new Point(x, y), isIgnoreCorner))//判断是否能走,能走则加入到vector中返回
            surroundPoints.push_back(new Point(x, y));
     
        return surroundPoints;
    }
    

    排序算法的应用

    在游戏中,排序算法一般都是用来做排名的,像下面这张图
    排名
    在这么多种排序算法中,一般是选择归并排序和快速排序,这两种是较优的,一般归并排序运用在对文件的排序,而快速排序适合大多数情况。

    在这里插入图片描述

    展开全文
  • 精华游戏算法整理.mht 经典的游戏算法全集
  • 主要介绍了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法,结合实例形式详细分析了游戏算法中针对碰撞检测的包盒矩形情况下的相关算法原理与操作注意事项,需要的朋友可以参考下
  • 主要介绍了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法,结合实例形式详细分析了圆形包盒情况下的碰撞检测算法相关原理与实现技巧,需要的朋友可以参考下
  • JSHTML5游戏常用算法之路径搜索算法随机迷宫算法详解【普里姆算法】随机搜索算法.pdf
  • 主要介绍了JS/HTML5游戏常用算法之碰撞检测 地图格子算法,结合实例形式详细分析了javascript碰撞检测算法的相关原理、实现技巧与操作注意事项,需要的朋友可以参考下
  • 游戏开发常用算法

    热门讨论 2013-03-01 21:17:13
    游戏开发常用算法,讲解一些常见的游戏开发算法……
  • 本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法。分享给大家供大家参考,具体如下: 原理可参考:https://www.jb51.net/article/152744.htm 完整实例代码如下: <!DOCTYPE html> <...
  • Java常用算法手册.zip

    2021-07-25 14:13:28
    接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用:最后,列举了算法的一些常见面试题。书中知识点覆盖全面,结构安排紧凑,讲解详细,实例丰富。全书对每一个知识点都给出了相 ...
  • 主要介绍了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法,结合实例形式详细分析了javascript针对凹多边形的分离轴检测算法相关概念、原理、实现技巧与操作注意事项,需要的朋友可以参考下
  • Java常用算法手册

    2017-11-06 15:43:25
    《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...
  • 游戏开发中常用算法

    万次阅读 多人点赞 2018-04-02 17:16:57
    堆排序:可用于做游戏排行榜前多少多少名,根据求最大的K个数还是最小的K个数来建最大堆和最小堆,再将最大/小堆的根节点和最后一个子叶节点交换,最后调整堆,重复刚才那两个步骤,直到得到K个数。当然,这种题也...

    内容会持续更新,有错误的地方欢迎指正,谢谢!

    1.与数组相关的算法:

    1. 快速排序(分治思想的应用):不是任何情况都适用,数据量小的话,还不如冒泡快,但快排的确很优秀。
    2. 堆排序:可用于做游戏排行榜前多少多少名,根据求最大的K个数还是最小的K个数来建最大堆和最小堆,再将最大/小堆的根节点和最后一个子叶节点交换,最后调整堆,重复刚才那两个步骤,直到得到K个数。当然,这种题也可以用红黑树实现的set来做。
    3. 二分查找:用于查找出分数为多少多少的玩家

    2.与树有关的算法

    四叉树、八叉树可用来检测大量物体之间的碰撞总次数。

    这里写图片描述

    3.与图有关的算法

    1.小型游戏可以用的简单的寻路算法:

    1. 随机寻路算法:当NPC不管是遇到障碍物还是遇到了边界(利用碰撞检测),都会随机选取一个前进的方向,继续行走
    2. 跟踪算法:当游戏中的主角进入到NPC 的“警戒区域”后,游戏的AI 可轻易获得目标的位置,然后控制NPC 对象移向被跟踪的对象
    3. 闪避算法:和跟踪算法完全相反,也就是当游戏中的主角进入到NPC 的“警戒区域”后,主角可以去追着NPC跑

    2.大型游戏一般使用A*寻路算法:使用最广泛的一种寻路算法,简单说一下A*寻路算法:

    这里写图片描述

    公式:f(n)=g(n)+h(n),g(n)表示从起点到任意点n的实际直线距离,h(n)表示任意顶点n到目标点的估算距离(常用曼哈顿距离公式用于估算h(n):|x1 - x2| + |y1 - y2|)

    把待处理的方格A存入一个”开启列表”,开启列表就是一个等待检查方格的列表;”关闭列表”中存放的都是不需要再次检查的方格。

    每次从OPEN列表中选择 f(n) 最小的节点将其加入CLOESE列表中,同时扩展相邻节点并将它们加入OPEN列表,可把OPEN列表看成一个优先队列,key值为 f(n),优先级最高的先出。

    最后直到把终点加入OPEN列表中,计算出指针指向就完事了。所以最后的路径就是,从终点开始沿着父指针不断往起点走,最后回到起始点,这样最短路径就找到了:

    这里写图片描述

    A*寻路的详细介绍请见:https://blog.csdn.net/billcyj/article/details/79462670

    3.DFS、BFS也常用于求最优方法这类问题

    展开全文
  • 游戏开发中常用数据结构与算法.ppt
  • 涵盖广泛 精炼的理论讲述搭配大量经典算法示例,学习查询兼而有之。 阐述到位 算法思想、算法实现和完整示例合理搭配,相辅相成。 示例完善 示例分析精准,代码注释精确,每段代码皆可通过... 11.2.1 取火柴游戏算法 ...
  • 日本游戏常用加密压缩算法.pdf
  • Flash游戏开发中常用算法.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,492
精华内容 24,996
关键字:

常用游戏算法