算法设计与分析-Week7

发表于 2018-10-16 | 更新于 2019-01-27

Gas Station

题目描述

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.

Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

解题思路

本题要找到一个加油站的下标，使得从这个加油站出发，走一圈可以回到这个加油站。

算法一：遍历所有加油站，从某个加油站开始，向前遍历一圈加油站，若能回到原点，则返回该加油站的下标；否则以下一个加油站为起点，继续向前遍历一圈加油站，直到找到能够返回原点的加油站或者遍历完所有加油站。时间复杂度为\(O(n^2)\)。
算法二：对以上算法进行改进，没有必要遍历所有的加油站。例如从某一个加油站i出发，到达加油站j之前停了下来，那么加油站i与j之间的所有加油站都无法到达j，那么这之间的加油站就不需要遍历了，下个起点可以选择加油站j+1，整个算法只需要遍历一遍加油站，时间复杂度为\(O(n)\)。

源代码

算法一

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int index = 0;
        int n = gas.size();
        vector<int> remain;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            remain.push_back(gas[i] - cost[i]);
            sum += gas[i] - cost[i];
        }
        if(sum < 0) return -1;
        while(index < n) {
            if(remain[index] < 0) {
                index++;
                continue;
            }
            sum = remain[index];
            int cur = index + 1;
            while((cur %= n) != index) {
                sum += remain[cur];
                if(sum < 0) break;
                cur++;
            }
            if(cur == index) return index;
            index++;
        }
        return -1;
    }
};

算法二

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int i, j, n = gas.size();

        /*
         * If start from i, stop before station x -> no station k from i + 1 to x - 1 can reach x.
         * Bcoz if so, i can reach k and k can reach x, then i reaches x. Contradiction.
         * Thus i can jump directly to x instead of i + 1, bringing complexity from O(n^2) to O(n).
         */
        // start from station i
        for (i = 0; i < n; i += j) {
            int gas_left = 0;
            // forward j stations
            for (j = 1; j <= n; j++) {
                int k = (i + j - 1) % n;
                gas_left += gas[k] - cost[k];
                if (gas_left < 0)
                    break;
            }
            if (j > n)
                return i;
        }

        return -1;
    }
};

算法设计与分析-Week6

发表于 2018-10-07 | 更新于 2019-01-27

Remove Invalid Parentheses

题目描述

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: “()())()”
Output: [“()()()”, “(())()”]

Example 2:

Input: “(a)())()”
Output: [“(a)()()”, “(a())()”]

Example 3:

Input: “)(“
Output: [“”]

解题思路

本题要在一个不合法的字符串中，去除最少的左右括号使字符串变得合法。
将给定字符串及其子字符串作为一个状态进行BFS，逐渐通过去掉括号的方式进行状态转移，为了避免所有括号都去掉一遍，我对去括号的方式做了一点改进，如果左括号多则只去左括号，如果右括号多则只去右括号。当发现合法的字符串时，将found置为true，使得不会再有字符串添加进队列，保证了去除最少的括号这一条件。

源代码

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        set<string> visited;
        vector<string> res;
        queue<string> q;
        q.push(s);
        visited.insert(s);
        bool found = false;
        while(!q.empty()) {
            string str = q.front();
            q.pop();
            int valid = isValid(str);
            if(valid == 0) {
                res.push_back(str);
                found = true;
                continue;
            }
            if(found) continue;
            for(int i = 0; i < str.length(); i++) {
                if(str[i] != '(' && str[i] != ')') continue;
                if((str[i] == '(' && valid > 0) || (str[i] == ')' && valid < 0)) {
                    string temp = str.substr(0, i) + str.substr(i + 1);
                    if(visited.count(temp) == 0) {
                        visited.insert(temp);
                        q.push(temp);
                    }
                }
            }
        }
        return res;
    }
    int isValid(string s) {
        int count = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(') count++;
            else if(s[i] == ')') count--;
            if(count < 0) return -1;
        }
        if(count > 0) return 1;
        else if(count == 0) return 0;
    }
};

算法设计与分析-Week5

发表于 2018-10-01 | 更新于 2019-01-27

Longest Increasing Path in a Matrix

题目描述

Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

解题思路

本题要在一个矩阵中找到一个最长的递增序列的长度。
用一个与所给矩阵大小相同的矩阵path，其中该矩阵的每个元素代表从该元素出发所能走出的最长递增序列的长度，那么只要记录这个矩阵的最大元素longest即为题目所求。遍历所给矩阵的每个元素，从该元素出发作DFS，每个元素有四个方向可以走，走之前先判断下一个位置是否越界以及下一个元素是否大于当前元素，如果是则对下一个位置进行DFS；如果当前位置的path值不为0，则说明当前位置已经经过DFS，直接返回即可；如果当前位置不存在满足条件的下一个位置，则说明当前位置是附近最大的一个元素，其path值为1。

源代码

class Solution {
public:
    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
        int longest = 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> path;
        for(int i = 0; i < m; i++) {
            vector<int> temp(n, 0);
            path.push_back(temp);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                longest = max(longest, dfs(matrix, i, j, path));
            }
        }
        return longest;
    }
    int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& path) {
        if(path[i][j] != 0) return path[i][j];
        int longest = 1;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int k = 0; k < 4; k++){
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if(x >= 0 && x < m && y >=0 && y < n && matrix[x][y] > matrix[i][j]) {
                int len = 1 + dfs(matrix, x, y, path);
                longest = max(longest, len);
            }
        }
        path[i][j] = longest;
        return longest;
    }
};

算法设计与分析-Week4

发表于 2018-09-25 | 更新于 2019-01-27

Recover Binary Search Tree

题目描述

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]
Output: [3,1,null,null,2]

Example 2:

Input: [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]

解题思路

题目描述的二叉搜索树有两个元素交换了位置，需要将其找出。由于二叉搜索树用中序遍历所得到的序列是递增的，因此对此二叉搜索树进行中序遍历得到的序列必定有两个元素不符合递增的规律，我在遍历过程中找出这两个元素，记为first和second，并在遍历完成后将其交换，以得到正确的二叉搜索树。
第一个错误的元素first必定大于其后的一个元素，第二个错误的元素second必定小于其前面的一个元素，因此我用一个preNode记录前一个元素，先找出第一个错误的元素first后，找出第二个错误的元素second，最后进行交换。

源代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* first;
    TreeNode* second;
    TreeNode* preNode;
public:
    Solution() {
        first = NULL;
        second = NULL;
        preNode = new TreeNode(INT_MIN);
    }
    void recoverTree(TreeNode* root) {
        traverse(root);
        /*交换两个错误的元素*/
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
    void traverse(TreeNode* root) {
        if(root == NULL) return;
        traverse(root->left);
        if(first == NULL && preNode->val > root->val) {
            first = preNode;
        }
        if(first != NULL && preNode->val > root->val) {
            second = root;
        }
        preNode = root;
        traverse(root->right);
    }
};

算法设计与分析-Week3

发表于 2018-09-17 | 更新于 2019-01-27

Jump Game II

题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Example 1:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note: You can assume that you can always reach the last index.

解题思路

题目所求的是从起点到终点的最少跳跃次数，数组的每一个整数表示的是当前位置所能跳跃的最大距离。这里我首先将起点所能到达的最远距离设为furthest，并用变量r保存这个最远点，由于在起点与r之间的每一个点我都可以跳，因此我对这中间的点进行遍历，根据这些点的最远跳跃距离找到第二次跳跃所能到达的最远点furthest，当遍历到达第一次跳跃的最远点r时，跳跃次数加一，此时肯定发生了一次跳跃，将r更新为最远点furthest，第二次跳跃的落点肯定在furthest之前；重复上面的操作，找到第三次及第n次跳跃所能到达的最远点furthest，当最远点比终点远时，再多跳一步即可到达终点。整个算法只需要遍历一次数组，因此时间复杂度为\(O(n)\)。

源代码

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() <= 1) return 0;
        int step = 0;
        int n = nums.size();
        int furthest = nums[0];
        int r = furthest;
        for(int i = 1; i < n; i++) {
            if(r >= n - 1) return step + 1;
            furthest = max(furthest, i + nums[i]);
            if(i >= r) {
                step++;
                r = furthest;
            }
        }
    }
};

算法设计与分析-Week2

发表于 2018-09-11 | 更新于 2019-01-27

Longest Palindromic Substring

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

解题思路

题目要求所给字符串的最长回文子字符串。

解法一

暴力求解。任选子字符串的两端，并验证该字符串是否为回文字符串，由于端点的两两选择需要\(O(n^2)\)的复杂度，验证字符串需要\(O(n)\)的复杂度，所以整个算法需要\(O(n^3)\)的时间复杂度。

解法二

并不需要对每个字符串都进行回文字符串的验证，假如一个字符串是回文字符串，那么如果其两侧的字符相同，则新的字符串也是回文字符串，这样就不用对新的字符串进行从头到尾的验证，从而把时间复杂度从\(O(n)\)降为\(O(1)\)。由所给的两个样例可以看出，回文字符串根据字符串的长度可分为奇偶两种，因此只要选好中心位置，沿着中心位置向两边进行扩展，就能得到该中心位置的最长回文字符串，遍历所有中心位置，就能得到最长的回文字符串，总的时间复杂度为\(O(n^2)\)。

源代码

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() == 0) return "";
        int start, length = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = maxLength(i, i, s);
            int len2 = maxLength(i, i + 1, s);
            if(len1 > len2 && len1 > length) {
                start = i - len1 / 2;
                length = len1;
            }
            else if(len1 < len2 && len2 > length) {
                start = i - len2 / 2 + 1;
                length = len2;
            }
        }
        return s.substr(start, length);
    }
    int maxLength(int left, int right, string s) {
        while(left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

算法设计与分析-Week1

发表于 2018-09-05 | 更新于 2019-01-27

Container With Most Water

题目描述

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解题思路

题目要求最大可装水的体积，可装水的体积取决于水桶两边的高以及底边的宽度，根据短板效应，可装水的高度不会超过两边的较短边的高度，因此可装水的体积=水桶两边的较短边的高度*底边的宽度。

解法一

暴力求解。将所有边两两组合并求体积，用两重循环即可解决，但时间复杂度为\(O(n^2)\)

解法二

先选取最左边和最右边两条边，记录此时的可装水的体积，由于该体积取决于两边的较短边，因此我们希望该较短边越长越好，于是我们将较短边替换成更内层的边，并计算新的可装水体积，与原来的体积作比较取较大值。最后当两边取到同一边时退出循环，得到最大可装水体积，时间复杂度为\(O(n)\)

源代码

class Solution {
public:
    int maxArea(vector<int>& height) {        

        int left = 0;
        int right = height.size() - 1;

        int max = containWater(height[left], height[right], right - left);
        while(left < right){
            if(height[left] < height[right]){
                left++;
                int temp = containWater(height[left], height[right], right - left);
                if(temp > max){
                    max = temp;
                }
            }
            else{
                right--;
                int temp = containWater(height[left], height[right], right - left);
                if(temp > max){
                    max = temp;
                }
            }
        }
        return max;
    }
    int containWater(int left, int right, int width){
        if(left < right) return left * width;
        else return right * width;
    }
};

Unity3d学习笔记-智能巡逻兵

发表于 2018-05-11

游戏设计要求

创建一个地图和若干巡逻兵(使用动画)；
每个巡逻兵走一个3~5个边的凸多边型，位置数据是相对地址。即每次确定下一个目标位置，用自己当前位置为原点计算；
巡逻兵碰撞到障碍物，则会自动选下一个点为目标；
巡逻兵在设定范围内感知到玩家，会自动追击玩家；
失去玩家目标后，继续巡逻；
计分：玩家每次甩掉一个巡逻兵计一分，与巡逻兵碰撞游戏结束；

程序设计要求

必须使用订阅与发布模式传消息
工厂模式生产巡逻兵

游戏实现

巡逻兵

为巡逻兵的父节点添加刚体和Capsule Collider，用于检测与玩家和墙壁的碰撞；为其子节点添加Box Collider，用于检测玩家是否进入巡逻兵的追踪范围。

DirectionController

用于存储东南西北四个方向，并控制巡逻兵转向

public class DirectionController : MonoBehaviour {
    private Dictionary<int, Vector3> directions;//存储东南西北四个方向，巡逻兵沿矩形路径巡逻
    // Use this for initialization
    void Awake () {
        directions = new Dictionary<int, Vector3>();
        directions.Add(0, new Vector3(1, 0, 0));
        directions.Add(1, new Vector3(0, 0, 1));
        directions.Add(2, new Vector3(-1, 0, 0));
        directions.Add(3, new Vector3(0, 0, -1));
    }
    
    public Vector3 RandomDirection()//随机获得一个方向
    {
        return directions[Random.Range(0, 4)];
    }

    public Vector3 ChangeDirection(Vector3 direction)//改变方向
    {
        if (direction.Equals(directions[0]))
        {
            return directions[1];
        }
        else if (direction.Equals(directions[1]))
        {
            return directions[2];
        }
        else if (direction.Equals(directions[2]))
        {
            return directions[3];
        }
        else if (direction.Equals(directions[3]))
        {
            return directions[0];
        }
        return RandomDirection();
    }
}

PatrolData

用于保存巡逻兵的基本信息

public class PatrolData : MonoBehaviour {
    public Vector3 position;        //记录巡逻兵的初始位置
    public bool follow;             //记录巡逻兵是否追踪玩家
    public GameObject player;       //记录玩家
    public Vector3 direction;       //记录巡逻兵的巡逻方向
    public float distance;          //记录巡逻兵沿着某一方向行走的距离
}

PatrolFactory

用于生产并初始化巡逻兵

public class PatrolFactory : MonoBehaviour {

    public GameObject patrolPrefab;
    
    public List<GameObject> GetPatrol()
    {
        GameObject newObject;
        List<GameObject> patrols=new List<GameObject>();
        int[] pos_x = { -15, 0, 15 };
        int[] pos_z = { -20, 20 };
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                newObject = Instantiate<GameObject>(patrolPrefab, new Vector3(pos_x[i], 0, pos_z[j]), Quaternion.identity);
                newObject.GetComponent<PatrolData>().position = new Vector3(pos_x[i], 0, pos_z[j]);
                newObject.GetComponent<PatrolData>().follow = false;
                newObject.GetComponent<PatrolData>().player = SSDirector.GetInstance().CurrentSceneController.GetPlayer();
                newObject.GetComponent<PatrolData>().direction = Singleton<DirectionController>.Instance.RandomDirection();
                newObject.GetComponent<PatrolData>().distance = 0;
                patrols.Add(newObject);
            }
        }
        return patrols;
    }    
}

PatrolAction

巡逻兵巡逻动作

public class PatrolAction : SSAction {

    private float speed = 5;
    private Vector3 direction;
    private float distance;
    private float turnSpeed = 10;
    public static PatrolAction GetSSAction()
    {
        PatrolAction action = ScriptableObject.CreateInstance<PatrolAction>();
        return action;
    }
    // Use this for initialization
    public override void Start()
    {
        direction = gameobject.GetComponent<PatrolData>().direction;
        distance = gameobject.GetComponent<PatrolData>().distance;        
    }

    // Update is called once per frame
    public override void Update () {
        if (gameobject.GetComponent<PatrolData>().follow)
        {
            this.destroy = true;
            this.callback.SSActionEvent(this,0,gameobject);
            return;
        }
        direction = gameobject.GetComponent<PatrolData>().direction;
        distance = gameobject.GetComponent<PatrolData>().distance;
        if (distance < 10)//巡逻兵移动
        {
            transform.position += direction * speed * Time.deltaTime;
            //将方向转换为四元数  
            Quaternion quaDir = Quaternion.LookRotation(direction, Vector3.up);
            //缓慢转动到目标点  
            transform.rotation = Quaternion.Lerp(transform.rotation, quaDir, Time.fixedDeltaTime * turnSpeed);
            gameobject.GetComponent<PatrolData>().distance += speed * Time.deltaTime;
            
        }
        else//巡逻兵转向
        {
            gameobject.GetComponent<PatrolData>().distance = 0;
            gameobject.GetComponent<PatrolData>().direction = 
                Singleton<DirectionController>.Instance.ChangeDirection(direction);
        }        
    }
}

PatrolFollowAction

巡逻兵追踪玩家动作

public class PatrolFollowAction : SSAction
{
    private GameObject player;
    private float speed = 5.8f;
    public static PatrolFollowAction GetSSAction()
    {
        PatrolFollowAction action = ScriptableObject.CreateInstance<PatrolFollowAction>();
        return action;
    }
    // Use this for initialization
    public override void Start()
    {
        player = gameobject.GetComponent<PatrolData>().player;
    }

    // Update is called once per frame
    public override void Update()
    {
        if (!gameobject.GetComponent<PatrolData>().follow)
        {
            this.destroy = true;
            this.callback.SSActionEvent(this,1,gameobject);
            return;
        }
        transform.position = Vector3.MoveTowards(transform.position, player.transform.position, speed * Time.deltaTime);
        transform.LookAt(player.transform.position);
    }
}

玩家

为玩家预制添加刚体和Capsule Collider，使玩家能够与其他物体发生碰撞。

UserGUI

接受玩家输入，控制玩家移动和使用技能

private void Update()
{
    if (action.GetGameState() == GameState.GAMEOVER) return;
    //获取方向键的偏移量
    translationX = Input.GetAxis("Horizontal");
    translationZ = Input.GetAxis("Vertical");
    //移动玩家
    action.PlayerMove(new Vector3(translationX,0,translationZ));
    if (coolTime<=0 && Input.GetButtonDown("Jump"))//如果不在冷却时间内，按下空格可以触发加速技能
    {
        action.SpeedUp();
        coolTime = 10;
    }
    else
    {
        coolTime -= Time.deltaTime;
    }
}
private void FixedUpdate()
{
    action.PlayerRotate(new Vector3(translationX, 0, translationZ));//玩家旋转方向
}

FirstController

实现玩家移动、转向和加速，部分代码如下

public void PlayerMove(Vector3 target)//玩家向目标移动
{
    if (gameState != GameState.GAMEOVER)
    {
        if (target.Equals(Vector3.zero))
        {
            player.GetComponent<Animator>().SetBool("run", false);
        }
        else
        {
            player.GetComponent<Animator>().SetBool("run", true);
            player.transform.position += target * moveSpeed * Time.deltaTime;
        }
    }
}
public void SpeedUp()//加速
{
    moveSpeed = 10;
    speedTime = 3;
}
public void PlayerRotate(Vector3 direction)
{
    if (gameState != GameState.GAMEOVER)
    {
        if (!direction.Equals(Vector3.zero))
        {
            //将方向转换为四元数  
            Quaternion quaDir = Quaternion.LookRotation(direction, Vector3.up);
            //缓慢转动到目标点  
            player.transform.rotation = Quaternion.Lerp(player.transform.rotation, quaDir, Time.fixedDeltaTime * turnSpeed);
        }
    }       
}

巡逻兵的碰撞检测

PatrolCollision

巡逻兵的Capsule Collider的碰撞检测，用于检测与玩家和墙壁的碰撞

public class PatrolCollision : MonoBehaviour {
    private void OnCollisionEnter(Collision collision)
    {
        if (collision.gameObject.tag == "Player")//当巡逻兵碰撞上玩家时，游戏结束
        {
            Singleton<GameEventManager>.Instance.PlayerCollide();
            gameObject.GetComponentInChildren<Animator>().SetTrigger("attack");
        }
        else//当巡逻兵碰撞到其他物体如墙壁时，转换方向
        {
            gameObject.GetComponent<PatrolData>().distance = 0;
            gameObject.GetComponent<PatrolData>().direction = 
                Singleton<DirectionController>.Instance.ChangeDirection(gameObject.GetComponent<PatrolData>().direction);
        }
    }    
}

PatrolFollowCollision

巡逻兵的Box Collider上的碰撞检测，用于检测玩家进入和退出碰撞盒，决定是否追踪玩家

public class PatrolFollowCollision : MonoBehaviour {
    private void OnTriggerEnter(Collider collider)//当玩家进入范围内时，追踪玩家
    {
        if (collider.gameObject.tag == "Player")
        {
            gameObject.GetComponent<BoxCollider>().size = new Vector3(15, 1, 15);//将碰撞盒变大防止反复进入和退出范围
            Singleton<GameEventManager>.Instance.PlayerClose(gameObject);
        }
    }
    private void OnTriggerExit(Collider collider)//当玩家脱离范围时，停止追踪
    {
        if (collider.gameObject.tag == "Player")
        {
            Singleton<GameEventManager>.Instance.Escape(gameObject);
            gameObject.GetComponent<BoxCollider>().size = new Vector3(10, 1, 10);//恢复碰撞盒大小
        }
    }
}

订阅与发布模式部分

GameEventManager

定义事件管理器，专门用于发布事件

public class GameEventManager : MonoBehaviour {

    public delegate void GameOver();
    public static event GameOver OnGameOver;

    public delegate void PatrolFollow(GameObject ob);
    public static event PatrolFollow OnPatrolFollow;

    public delegate void PlayerEscape(GameObject ob);
    public static event PlayerEscape OnPlayerEscape;

    public void PlayerCollide()//玩家碰撞
    {
        if (OnGameOver != null)
        {
            OnGameOver();
        }
    }

    public void PlayerClose(GameObject ob)//玩家靠近巡逻兵
    {
        if (OnPatrolFollow != null)
        {
            OnPatrolFollow(ob);
        }
    }

    public void Escape(GameObject ob)//玩家脱离巡逻兵
    {
        if (OnPlayerEscape != null)
        {
            OnPlayerEscape(ob);
        }
    }
}

FirstController

场景控制器作为订阅者，只要相应事件发生，就会调用注册的方法

void OnEnable()
{
    GameEventManager.OnGameOver += GameOver;
    GameEventManager.OnPatrolFollow += Follow;
    GameEventManager.OnPlayerEscape += Escape;
}
void OnDisable()
{
    GameEventManager.OnGameOver -= GameOver;
    GameEventManager.OnPatrolFollow -= Follow;
    GameEventManager.OnPlayerEscape -= Escape;
}
public void GameOver()//游戏结束
{
    gameState = GameState.GAMEOVER;
    player.GetComponent<Animator>().SetBool("death", true);
    player.GetComponent<Animator>().SetTrigger("dieTrigger");
    actionManager.DestroyAllActions();
    foreach(GameObject patrol in Patrols)
    {
        patrol.GetComponentInChildren<Animator>().SetBool("run", false);
        patrol.transform.localEulerAngles = new Vector3(0, patrol.transform.localEulerAngles.y, 0);
        patrol.transform.position = new Vector3(patrol.transform.position.x, 0, patrol.transform.position.z);
    }
}
void Follow(GameObject ob)//巡逻兵跟随
{
    ob.GetComponentInParent<PatrolData>().follow = true;
}
void Escape(GameObject ob)//玩家脱离
{
    ob.GetComponentInParent<PatrolData>().follow = false;
    Singleton<ScoreRecorder>.Instance.AddScore();
}

具体代码和游戏视频请参考我的github：Patrol
本次实验用到了订阅与发布模式，这种模式使得游戏的各个部分相对独立，随着工程的不断扩展变大，程序代码也会不断变多，使用这种方式来减少各部分之间的耦合，就变得非常有意义。

Li Jiangtao

48 日志

14 标签