By

文章目錄
  1. 1. 前言
  2. 2. 红点系统
    1. 2.1. 红点系统需求
    2. 2.2. 红点系统设计
    3. 2.3. 前缀树
      1. 2.3.1. 前缀树实战
    4. 2.4. 红点系统实战
      1. 2.4.1. 红点系统类说明
      2. 2.4.2. 实战
  3. 3. 重点知识
  4. 4. Reference
  5. 5. Github

前言

游戏开发过程中为了提示玩家有可操作数据，往往会采用显示红点的方式，红点会散布到游戏的各个角落，如果项目初期没有一个好的红点系统，后期维护开发中往往会有数不清的红点bug以及不必要的红点刷新开销。本章节真是为了实现一套高效且高度可扩展和可维护的红点系统而编写的。

红点系统

红点系统需求

在开始设计和编写我们需要的红点系统前，让我们先理清下红点的需求:

  1. 单个红点可能受多个游戏逻辑因素影响
  2. 内层红点可以影响外层红点可以不影响外层红点
  3. 红点显示逻辑会受功能解锁和游戏数据流程影响
  4. 红点样式多种多样(e.g. 1. 纯红点 2. 纯数字红点 3. 新红点 4. 混合红点等)
  5. 红点结果计算的数据来源可以是客户端计算红点也可以是服务器已经算好的红点结论(有时候为了优化数据通信量，有些功能的详情会按需请求导致客户端无法直接计算红点，采取后端直接通知红点的方式)
  6. 红点分静态红点(界面上固定存在的)和动态红点(列表里数量繁多的)
  7. 数据变化会触发红点频繁逻辑运算(有时候还会触发重复运算)导致GC和时间占用
  8. 红点影响因素比较多，查询的时候缺乏可视化高效的查询手段

红点系统设计

针对上面的红点需求，我通过以下设计来一一解决:

  1. 采用前缀树数据结构，从红点命名上解决红点父子定义关联问题
  2. 红点运算单元采用最小单元化定义，采用组合定义方式组装红点影响因素，从而实现高度自由的红点运算逻辑组装
  3. 红点运算单元作为红点影响显示的最小单元，每一个都会对应逻辑层面的一个计算代码，从而实现和逻辑层关联实现自定义解锁和计算方式
  4. 红点运算结果按红点运算单元为单位，采用标脏加延迟计算的方式避免重复运算和结果缓存
  5. 红点运算单元支持多种显示类型定义(e.g. 1. 纯红点 2. 纯数字红点 3. 新红点 4. 混合红点等)，红点最终显示类型由所有影响他的红点运算单元计算结果组合而成(e.g. 红点运算单元1(新红点类型)+红点运算单元2(数字红点类型)=新红点类型)
  6. 除了滚动列表里数量过多的红点采用界面上自行计算的方式，其他红点全部采用静态红点预定义的方式，全部提前定义好红点名以及红点运算单元组成和父子关系等数据
  7. 编写自定义EditorWindow实现红点数据全面可视化提升红点系统可维护性

前缀树

在真正实战编写红点系统之前，让我们先了解实现一版前缀树，后续会用到红点系统里解决红点父子关联问题。

trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

前缀树结构

从上面可以看出前缀树也是树机构，但不是通常说的二叉树。

前缀树最典型的应用就是输入法单次推断，比如我们输入周星两个字，输入法会根据用户输入的周星两个字去查询词库，看有哪些匹配的词语进行人性化引导提示显示。而这个查询词库匹配的过程就要求很高的查询效率，而前缀树正是完美解决了这一问题。前缀树通过先搜索周节点，然后查找到周节点后继续在周节点下搜寻星字节点，查到星字节点后，以星字节点继续往下搜索匹配出所有符合的单词进行显示，从而通过O(N)的方式实现了快速的单词匹配查询。

前缀树实战

Trie.cs(抽象前缀树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UnityEngine;

/// <summary>
/// 前缀树
/// </summary>
public class Trie
{
    /// <summary>
    /// 单词分隔符
    /// </summary>
    public char Separator
    {
        get;
        private set;
    }

    /// <summary>
    /// 单词数量
    /// </summary>
    public int WorldCount
    {
        get;
        private set;
    }

    /// <summary>
    /// 树深度
    /// </summary>
    public int TrieDeepth
    {
        get;
        private set;
    }

    /// <summary>
    /// 根节点
    /// </summary>
    public TrieNode RootNode
    {
        get;
        private set;
    }

    /// <summary>
    /// 单词列表(用于缓存分割结果，优化单个单词判定时重复分割问题)
    /// </summary>
    private List<string> mWordList;

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="separator"></param>
    public Trie(char separator = '|')
    {
        Separator = separator;
        WorldCount = 0;
        TrieDeepth = 0;
        RootNode = ObjectPool.Singleton.pop<TrieNode>();
        RootNode.Init("Root", null, this, 0, false);
        mWordList = new List<string>();
    }

    /// <summary>
    /// 添加单词
    /// </summary>
    /// <param name="word"></param>
    public void AddWord(string word)
    {
        mWordList.Clear();
        var words = word.Split(Separator);
        mWordList.AddRange(words);
        var length = mWordList.Count;
        var node = RootNode;
        for (int i = 0; i < length; i++)
        {
            var spliteWord = mWordList[i];
            var isLast = i == (length - 1);
            if (!node.ContainWord(spliteWord))
            {
                node = node.AddChildNode(spliteWord, isLast);
            }
            else
            {
                node = node.GetChildNode(spliteWord);
                if(isLast)
                {
                    Debug.Log($"添加重复单词:{word}");
                }
            }
        }
    }

    /// <summary>
    /// 移除指定单词
    /// Note:
    /// 仅当指定单词存在时才能移除成功
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public bool RemoveWord(string word)
    {
        if(string.IsNullOrEmpty(word))
        {
            Debug.LogError($"不允许移除空单词!");
            return false;
        }
        var wordNode = GetWordNode(word);
        if(wordNode == null)
        {
            Debug.LogError($"找不到单词:{word}的节点信息，移除单词失败!");
            return false;
        }
        if(wordNode.IsRoot)
        {
            Debug.LogError($"不允许删除根节点!");
            return false;
        }
        // 从最里层节点开始反向判定更新和删除
        if(!wordNode.IsTail)
        {
            Debug.LogError($"单词:{word}的节点不是单词节点，移除单词失败!");
            return false;
        }
        // 删除的节点是叶子节点时要删除节点并往上递归更新节点数据
        // 反之只更新标记为非单词节点即可结束
        if(wordNode.ChildCount > 0)
        {
            wordNode.IsTail = false;
            return true;
        }
        wordNode.RemoveFromParent();
        // 网上遍历更新节点信息
        var node = wordNode.Parent;
        while(node != null && !node.IsRoot)
        {
            // 没有子节点且不是单词节点则直接删除
            if(node.ChildCount == 0 && !node.IsTail)
            {
                node.RemoveFromParent();
            }
            node = node.Parent;
            // 有子节点则停止往上更新
            if(node.ChildCount > 0)
            {
                break;
            }
        }
        return true;
    }

    /// <summary>
    /// 获取指定字符串的单词节点
    /// Note:
    /// 只有满足每一层且最后一层是单词的节点才算有效单词节点
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public TrieNode GetWordNode(string word)
    {
        if (string.IsNullOrEmpty(word))
        {
            Debug.LogError($"无法获取空单词的单次节点!");
            return null;
        }
        // 从最里层节点开始反向判定更新和删除
        var wordArray = word.Split(Separator);
        var node = RootNode;
        foreach(var spliteWord in wordArray)
        {
            var childNode = node.GetChildNode(spliteWord);
            if (childNode != null)
            {
                node = childNode;
            }
            else
            {
                break;
            }
        }
        if(node == null || !node.IsTail)
        {
            Debug.Log($"找不到单词:{word}的单词节点!");
            return null;
        }
        return node;
    }

    /// <summary>
    /// 有按指定单词开头的词语
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public bool StartWith(string word)
    {
        if (string.IsNullOrEmpty(word))
        {
            return false;
        }
        mWordList.Clear();
        var wordArray = word.Split(Separator);
        mWordList.AddRange(wordArray);
        return FindWord(RootNode, mWordList);
    }

    /// <summary>
    /// 查找单词
    /// </summary>
    /// <param name="trieNode"></param>
    /// <param name="wordList"></param>
    /// <returns></returns>
    private bool FindWord(TrieNode trieNode, List<string> wordList)
    {
        if (wordList.Count == 0)
        {
            return true;
        }
        var firstWord = wordList[0];
        if (!trieNode.ContainWord(firstWord))
        {
            return false;
        }
        var childNode = trieNode.GetChildNode(firstWord);
        wordList.RemoveAt(0);
        return FindWord(childNode, wordList);
    }

    /// <summary>
    /// 单词是否存在
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public bool ContainWord(string word)
    {
        if(string.IsNullOrEmpty(word))
        {
            return false;
        }
        mWordList.Clear();
        var wordArray = word.Split(Separator);
        mWordList.AddRange(wordArray);
        return MatchWord(RootNode, mWordList);
    }

    /// <summary>
    /// 匹配单词(单词必须完美匹配)
    /// </summary>
    /// <param name="trieNode"></param>
    /// <param name="wordList"></param>
    /// <returns></returns>
    private bool MatchWord(TrieNode trieNode, List<string> wordList)
    {
        if (wordList.Count == 0)
        {
            return trieNode.IsTail;
        }
        var firstWord = wordList[0];
        if (!trieNode.ContainWord(firstWord))
        {
            return false;
        }
        var childNode = trieNode.GetChildNode(firstWord);
        wordList.RemoveAt(0);
        return MatchWord(childNode, wordList);
    }

    /// <summary>
    /// 获取所有单词列表
    /// </summary>
    /// <returns></returns>
    public List<string> GetWordList()
    {
        return GetNodeWorldList(RootNode, string.Empty);
    }

    /// <summary>
    /// 获取节点单词列表
    /// </summary>
    /// <param name="trieNode"></param>
    /// <param name="preFix"></param>
    /// <returns></returns>
    private List<string> GetNodeWorldList(TrieNode trieNode, string preFix)
    {
        var wordList = new List<string>();
        foreach (var childNodeKey in trieNode.ChildNodesMap.Keys)
        {
            var childNode = trieNode.ChildNodesMap[childNodeKey];
            string word;
            if (trieNode.IsRoot)
            {
                word = $"{preFix}{childNodeKey}";
            }
            else
            {
                word = $"{preFix}{Separator}{childNodeKey}";
            }
            if (childNode.IsTail)
            {
                wordList.Add(word);
            }
            if (childNode.ChildNodesMap.Count > 0)
            {
                var childNodeWorldList = GetNodeWorldList(childNode, word);
                wordList.AddRange(childNodeWorldList);
            }
        }
        return wordList;
    }

    /// <summary>
    /// 打印树形节点
    /// </summary>
    public void PrintTreeNodes()
    {
        PrintNodes(RootNode, 1);
    }

    /// <summary>
    /// 打印节点
    /// </summary>
    /// <param name="node"></param>
    /// <param name="depth"></param>
    private void PrintNodes(TrieNode node, int depth = 1)
    {
        var count = 1;
        foreach (var childeNode in node.ChildNodesMap)
        {
            Console.Write($"{childeNode.Key}({depth}-{count})");
            count++;
        }
        Console.WriteLine();
        foreach (var childeNode in node.ChildNodesMap)
        {
            PrintNodes(childeNode.Value, depth + 1); 
        }
    }
}

TrieNode.cs(前缀树节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// TrieNode.cs
/// 前缀树节点类
/// </summary>
public class TrieNode : IRecycle
{
    /// <summary>
    /// 节点字符串
    /// </summary>
    public string NodeValue
    {
        get;
        private set;
    }

    /// <summary>
    /// 父节点
    /// </summary>
    public TrieNode Parent
    {
        get;
        private set;
    }

    /// <summary>
    /// 所属前缀树
    /// </summary>
    public Trie OwnerTree
    {
        get;
        private set;
    }

    /// <summary>
    /// 节点深度(根节点为0)
    /// </summary>
    public int Depth
    {
        get;
        private set;
    }

    /// <summary>
    /// 是否是单词节点
    /// </summary>
    public bool IsTail
    {
        get;
        set;
    }

    /// <summary>
    /// 是否是根节点
    /// </summary>
    public bool IsRoot
    {
        get
        {
            return Parent == null;
        }
    }

    /// <summary>
    /// 子节点映射Map<节点字符串, 节点对象>
    /// </summary>
    public Dictionary<string, TrieNode> ChildNodesMap
    {
        get;
        private set;
    }

    /// <summary>
    /// 子节点数量
    /// </summary>
    public int ChildCount
    {
        get
        {
            return ChildNodesMap.Count;
        }
    }

    public TrieNode()
    {
        ChildNodesMap = new Dictionary<string, TrieNode>();
    }

    public void OnCreate()
    {
        NodeValue = null;
        Parent = null;
        OwnerTree = null;
        Depth = 0;
        IsTail = false;
        ChildNodesMap.Clear();
    }

    /// <summary>
    /// 初始化数据
    /// </summary>
    /// <param name="value">字符串</param>
    /// <param name="parent">父节点</param>
    /// <param name="ownerTree">所属前缀树</param>
    /// <param name="depth">节点深度</param>
    /// <param name="isTail">是否是单词节点</param>
    public void Init(string value, TrieNode parent, Trie ownerTree, int depth, bool isTail = false)
    {
        NodeValue = value;
        Parent = parent;
        OwnerTree = ownerTree;
        Depth = depth;
        IsTail = isTail;
    }

    public void OnDispose()
    {
        NodeValue = null;
        Parent = null;
        OwnerTree = null;
        Depth = 0;
        IsTail = false;
        ChildNodesMap.Clear();
    }

    /// <summary>
    /// 添加子节点
    /// </summary>
    /// <param name="nodeWord"></param>
    /// <param name="isTail"></param>
    /// <returns></returns>
    public TrieNode AddChildNode(string nodeWord, bool isTail)
    {
        TrieNode node;
        if (ChildNodesMap.TryGetValue(nodeWord, out node))
        {
            Debug.Log($"节点字符串:{NodeValue}已存在字符串:{nodeWord}的子节点,不重复添加子节点!");
            return node;
        }
        node = ObjectPool.Singleton.pop<TrieNode>();
        node.Init(nodeWord, this, OwnerTree, Depth + 1, isTail);
        ChildNodesMap.Add(nodeWord, node);
        return node;
    }

    /// <summary>
    /// 移除指定子节点
    /// </summary>
    /// <param name="nodeWord"></param>
    /// <returns></returns>
    public bool RemoveChildNodeByWord(string nodeWord)
    {
        var childNode = GetChildNode(nodeWord);
        return RemoveChildNode(childNode);
    }

    /// <summary>
    /// 移除指定子节点
    /// </summary>
    /// <param name="childNode"></param>
    /// <returns></returns>
    public bool RemoveChildNode(TrieNode childNode)
    { 
        if(childNode == null)
        {
            Debug.LogError($"无法移除空节点!");
            return false;
        }
        var realChildNode = GetChildNode(childNode.NodeValue);
        if(realChildNode != childNode)
        {
            Debug.LogError($"移除的子节点单词:{childNode.NodeValue}对象不是同一个,移除子节点失败!");
            return false;
        }
        ChildNodesMap.Remove(childNode.NodeValue);
        ObjectPool.Singleton.push<TrieNode>(childNode);
        return true;
    }

    /// <summary>
    /// 当前节点从父节点移除
    /// </summary>
    /// <returns></returns>
    public bool RemoveFromParent()
    {
        if(IsRoot)
        {
            Debug.LogError($"当前节点是根节点，不允许从父节点移除，从父节点移除当前节点失败!");
            return false;
        }
        return Parent.RemoveChildNode(this);
    }

    /// <summary>
    /// 获取指定字符串的子节点
    /// </summary>
    /// <param name=""></param>
    /// <param name=""></param>
    /// <returns></returns>
    public TrieNode GetChildNode(string nodeWord)
    {
        TrieNode trieNode;
        if (!ChildNodesMap.TryGetValue(nodeWord, out trieNode))
        {
            Debug.Log($"节点字符串:{NodeValue}找不到子节点字符串:{nodeWord},获取子节点失败!");
            return null;
        }
        return trieNode;
    }

    /// <summary>
    /// 是否包含指定字符串的子节点
    /// </summary>
    /// <param name=""></param>
    /// <param name=""></param>
    /// <returns></returns>
    public bool ContainWord(string nodeWord)
    {
        return ChildNodesMap.ContainsKey(nodeWord);
    }

    /// <summary>
    /// 获取当前节点构成的单词
    /// Note:
    /// 不管当前节点是否是单词节点,都返回从当前节点回溯到根节点拼接的单词
    /// 若当前节点为根节点，则返回根节点的字符串(默认为"Root")
    /// </summary>
    /// <returns></returns>
    public string GetFullWord()
    {
        var trieNodeWord = NodeValue;
        var node = Parent;
        while(node != null && !node.IsRoot)
        {
            trieNodeWord = $"{node.NodeValue}{OwnerTree.Separator}{trieNodeWord}";
            node = node.Parent;
        }
        return trieNodeWord;
    }
}

TrieEditorWindow.cs(前缀树测试窗口)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEditor;
using UnityEngine;

/// <summary>
/// TrieEditorWindow.cs
/// 前缀树窗口
/// </summary>
public class TrieEditorWindow : EditorWindow
{
    /// <summary>
    /// 居中Button GUI Style
    /// </summary>
    private GUIStyle mButtonMidStyle;

    /// <summary>
    /// 前缀树
    /// </summary>
    private Trie mTrie;

    /// <summary>
    /// 当前滚动位置
    /// </summary>
    private Vector2 mCurrentScrollPos;

    /// <summary>
    /// 输入单词
    /// </summary>
    private string mInputWord;

    /// <summary>
    /// 节点展开Map<节点单词全名, 是否展开> 
    /// </summary>
    private Dictionary<string, bool> mTrieNodeUnfoldMap = new Dictionary<string, bool>();

    /// <summary>
    /// 前缀树单词列表
    /// </summary>
    private List<string> mTrieWordList;

    [MenuItem("Tools/前缀树测试窗口")]
    static void Init()
    {
        TrieEditorWindow window = (TrieEditorWindow)EditorWindow.GetWindow(typeof(TrieEditorWindow), false, "前缀树测试窗口");
        window.Show();
    }

    void OnGUI()
    {
        InitGUIStyle();
        InitData();
        mCurrentScrollPos = EditorGUILayout.BeginScrollView(mCurrentScrollPos);
        EditorGUILayout.BeginVertical();
        DisplayTrieOperationArea();
        DisplayTrieContentArea();
        DisplayTrieWordsArea();
        EditorGUILayout.EndVertical();
        EditorGUILayout.EndScrollView();
    }

    /// <summary>
    /// 初始化GUIStyle
    /// </summary>
    private void InitGUIStyle()
    {
        if(mButtonMidStyle == null)
        {
            mButtonMidStyle = new GUIStyle("ButtonMid");
        }
    }

    /// <summary>
    /// 初始化数据
    /// </summary>
    private void InitData()
    {
        if (mTrie == null)
        {
            mTrie = new Trie();
            mTrieWordList = null;
        }
    }

    /// <summary>
    /// 更新前缀树单词列表
    /// </summary>
    private void UpdateTrieWordList()
    {
        mTrieWordList = mTrie.GetWordList();
    }

    /// <summary>
    /// 显示前缀树操作区域
    /// </summary>
    private void DisplayTrieOperationArea()
    {
        EditorGUILayout.BeginHorizontal("box");
        EditorGUILayout.LabelField("单词:", GUILayout.Width(40f), GUILayout.Height(20f));
        mInputWord = EditorGUILayout.TextField(mInputWord, GUILayout.ExpandWidth(true), GUILayout.Height(20f));
        if(GUILayout.Button("添加", GUILayout.Width(120f), GUILayout.Height(20f)))
        {
            if (string.IsNullOrEmpty(mInputWord))
            {
                Debug.LogError($"不能允许添加空单词!");
            }
            else
            {
                mTrie.AddWord(mInputWord);
                UpdateTrieWordList();
            }
        }
        if (GUILayout.Button("删除", GUILayout.Width(120f), GUILayout.Height(20f)))
        {
            if(string.IsNullOrEmpty(mInputWord))
            {
                Debug.LogError($"不能允许删除空单词!");
            }
            else
            {
                mTrie.RemoveWord(mInputWord);
            }
        }
        EditorGUILayout.EndHorizontal();
    }

    /// <summary>
    /// 绘制前缀树内容
    /// </summary>
    private void DisplayTrieContentArea()
    {
        EditorGUILayout.BeginVertical("box");
        EditorGUILayout.LabelField("前缀树节点信息", mButtonMidStyle, GUILayout.ExpandWidth(true), GUILayout.Height(20f));
        DisplayTrieNode(mTrie.RootNode);
        EditorGUILayout.EndVertical();
    }

    /// <summary>
    /// 显示一个节点
    /// </summary>
    /// <param name="trieNode"></param>
    private void DisplayTrieNode(TrieNode trieNode)
    {
        var nodeFullWord = trieNode.GetFullWord();
        if(!mTrieNodeUnfoldMap.ContainsKey(nodeFullWord))
        {
            mTrieNodeUnfoldMap.Add(nodeFullWord, true);
        }
        EditorGUILayout.BeginHorizontal("box");
        GUILayout.Space(trieNode.Depth * 20);
        var displayName = $"{trieNode.NodeValue}({trieNode.Depth})";
        if (trieNode.ChildCount > 0)
        {
            mTrieNodeUnfoldMap[nodeFullWord] = EditorGUILayout.Foldout(mTrieNodeUnfoldMap[nodeFullWord], displayName);
        }
        else
        {
            EditorGUILayout.LabelField(displayName);
        }
        EditorGUILayout.EndHorizontal();
        if(mTrieNodeUnfoldMap[nodeFullWord] && trieNode.ChildCount > 0)
        {
            var childNodeValueList = trieNode.ChildNodesMap.Keys.ToList();
            foreach(var childNodeValue in childNodeValueList)
            {
                var childNode = trieNode.GetChildNode(childNodeValue);
                DisplayTrieNode(childNode);
            }
        }
    }

    /// <summary>
    /// 显示前缀树单词区域
    /// </summary>
    private void DisplayTrieWordsArea()
    {
        EditorGUILayout.BeginVertical("box");
        EditorGUILayout.LabelField("前缀树单词信息", mButtonMidStyle, GUILayout.ExpandWidth(true), GUILayout.Height(20f));
        if(mTrieWordList != null)
        {
            foreach (var word in mTrieWordList)
            {
                EditorGUILayout.LabelField(word, GUILayout.ExpandWidth(true), GUILayout.Height(20f));
            }
        }
        EditorGUILayout.EndVertical();
    }
}

TrieEditorPreview

从上面可以看到我们成功通过字符串+|分割的方式，分析出了我们添加的单词的在前缀树中的关联关系。

红点系统实战

红点系统类说明

RedDotName.cs — 红点名定义(通过前缀树表达父子关系，所有静态红点都一开始定义在这里)

RedDotInfo.cs — 红点信息类(包含红点运算单元组成信息)

RedDotUnit.cs — 红点运算单元枚举定义(所有静态红点需要参与运算的最小单元都定义在这里)

RedDotUnitInfo.cs — 红点运算单元类(只是当做刷新机制的无需传递计算回调)

RedDotType.cs — 红点类型(用于支持上层各类复杂的红点显示方式 e.g. 纯红点，纯数字，新红点等)

RedDotModel.cs — 红点数据层(所有的红点名信息和红点运算单元信息全部在这一层初始化)

RedDotManager.cs — 红点单例管理类(提供统一的红点管理，红点运算单元计算结果缓存，红点绑定回调等流程)

RedDotUtilities.cs — 红点辅助类(一些通用方法还有逻辑层的红点运算方法定义在这里)

GameModel.cs — 逻辑数据层存储模拟

RedDotEditorWindow.cs — 红点系统可视化窗口(方便快速可视化查看红点运行状态和相关信息)

RedDotStyles.cs — 红点Editor显示Style定义

Trie.cs — 前缀树(用于红点名通过字符串的形式表达出层级关系)

TrieNode.cs — 前缀树节点

实战

由于代码部分比较多，这里就不放源代码了，直接看实战效果图，源码可以在最后的Github链接找到。

初始化后的红点前缀树状态:

RedDotTriePreiview

点击标记功能1新按钮后:

RedDotTriePreiviewAfterMarkFunc1New

点击菜单->背包->点击增加1个当前页签的新道具，切换页签并点击操作数据增加:

BackpackUIOperation

背包操作完后，主界面状态:

MainUIAfterBackpackOperation

背包操作完后，红点可视化前缀树:

RedDotTrieAfterBackpackUIOperation

背包增加操作后，MAIN_UI_MENU红点名的红点可视化详情:

RedDotDetailAfterBackpackOperation

所有红点运算单元详情:

AllRedDotUnitInfoPreview0

通过菜单->背包->点击减少1个当前页签的新道具，切换页签点击并操作数据减少:

BackpackUIOperationAfterReduce

背包减少操作后,红点可视化前缀树:

RedDotTriePreviewAfterBackpackReduce

从上面的测试可以看到，我们通过定义红点名，红点运算单元相关数据，成功的分析出了红点层级关系(利用前缀树)以及红点名与红点运算单元的组合关系。

通过编写RedDotEditorWindow成功将红点数据详情可视化的显示在了调试窗口上，通过调试窗口我们可以快速的查看所有红点名和红点运算单元的相关数据，从而实现快速的调试和查看功能。

上层逻辑只需关心红点名和红点运算单元的定义以及红点名在逻辑层的绑定刷新即可。

这里我放一部分红点名和红点运算单元的初始化相关代码，详情参考Github源码:

  • 红点系统的初始化和更新驱动

    GameLauncher.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void Awake()
{
    mSingleton = this;
    RedDotModel.Singleton.Init();
    RedDotManager.Singleton.Init();
    // 所有数据初始化完成后触发一次红点运算单元计算
    RedDotManager.Singleton.DoAllRedDotUnitCaculate();
}

public void Update()
{
    RedDotManager.Singleton.Update();        
}
******

  • 红点数据定义初始化

    RedDotModel.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/// <summary>
/// 初始化
/// </summary>
public void Init()
{
    if (IsInitCompelte)
    {
        Debug.LogError($"请勿重复初始化!");
        return;
    }
    // 优先初始化红点单元，现在改成通过红点名正向配置红点单元组成，而非反向红点单元定义影响红点名组成
    InitRedDotUnitInfo();
    InitRedDotInfo();
    InitRedDotTree();
    // InitRedDotUnitNameMap必须在InitRedDotInfo之后调用，因为用到了前面的数据
    UpdateRedDotUnitNameMap();
    IsInitCompelte = true;
}

/// <summary>
/// 初始化红点运算单元信息
/// </summary>
private void InitRedDotUnitInfo()
{
    // 构建添加所有游戏里的红点运算单元信息
    AddRedDotUnitInfo(RedDotUnit.NEW_FUNC1, "动态新功能1解锁", RedDotUtilities.CaculateNewFunc1, RedDotType.NEW);
    AddRedDotUnitInfo(RedDotUnit.NEW_FUNC2, "动态新功能2解锁", RedDotUtilities.CaculateNewFunc2, RedDotType.NEW);
    AddRedDotUnitInfo(RedDotUnit.NEW_ITEM_NUM, "新道具数", RedDotUtilities.CaculateNewItemNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.NEW_RESOURCE_NUM, "新资源数", RedDotUtilities.CaculateNewResourceNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.NEW_EQUIP_NUM, "新装备数", RedDotUtilities.CaculateNewEquipNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.NEW_PUBLIC_MAIL_NUM, "新公共邮件数", RedDotUtilities.CaculateNewPublicMailNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.NEW_BATTLE_MAIL_NUM, "新战斗邮件数", RedDotUtilities.CaculateNewBattleMailNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.NEW_OTHER_MAIL_NUM, "新其他邮件数", RedDotUtilities.CaculateNewOtherMailNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.PUBLIC_MAIL_REWARD_NUM, "公共邮件可领奖数", RedDotUtilities.CaculateNewPublicMailRewardNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.BATTLE_MAIL_REWARD_NUM, "战斗邮件可领奖数", RedDotUtilities.CaculateNewBattleMailRewardNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.WEARABLE_EQUIP_NUM, "可穿戴装备数", RedDotUtilities.CaculateWearableEquipNum, RedDotType.NUMBER);
    AddRedDotUnitInfo(RedDotUnit.UPGRADEABLE_EQUIP_NUM, "可升级装备数", RedDotUtilities.CaculateUpgradeableEquipNum, RedDotType.NUMBER);
}

/// <summary>
/// 初始化红点信息
/// </summary>
private void InitRedDotInfo()
{
    /// Note:
    /// 穷举的好处是足够灵活
    /// 缺点是删除最里层红点运算单元需要把外层所有影响到的红点名相关红点运算单元配置删除
    /// 调用AddRedDotInfo添加游戏所有静态红点信息
    InitMainUIRedDotInfo();
    InitBackpackUIRedDotInfo();
    InitMailUIRedDotInfo();
    InitEquipUIRedDotInfo();
}

/// <summary>
/// 初始化主界面红点信息
/// </summary>
private void InitMainUIRedDotInfo()
{
    RedDotInfo redDotInfo;
    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_NEW_FUNC1, "主界面新功能1红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_FUNC1);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_NEW_FUNC2, "主界面新功能2红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_FUNC2);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_MENU, "主界面菜单红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_ITEM_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_RESOURCE_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_EQUIP_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_MAIL, "主界面邮件红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_PUBLIC_MAIL_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_BATTLE_MAIL_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_OTHER_MAIL_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.PUBLIC_MAIL_REWARD_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_MENU_EQUIP, "主界面菜单装备红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.WEARABLE_EQUIP_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.UPGRADEABLE_EQUIP_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIN_UI_MENU_BACKPACK, "主界面菜单背包红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_ITEM_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_RESOURCE_NUM);
}

/// <summary>
/// 初始化背包界面红点信息
/// </summary>
private void InitBackpackUIRedDotInfo()
{
    RedDotInfo redDotInfo;
    redDotInfo = AddRedDotInfo(RedDotNames.BACKPACK_UI_ITEM_TAG, "背包界面道具页签红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_ITEM_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.BACKPACK_UI_RESOURCE_TAG, "背包界面资源页签红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_RESOURCE_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.BACKPACK_UI_EQUIP_TAG, "背包界面装备页签红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_EQUIP_NUM);
}

/// <summary>
/// 初始化邮件界面红点信息
/// </summary>
private void InitMailUIRedDotInfo()
{
    RedDotInfo redDotInfo;
    redDotInfo = AddRedDotInfo(RedDotNames.MAIL_UI_PUBLIC_MAIL, "邮件界面公共邮件红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_PUBLIC_MAIL_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.PUBLIC_MAIL_REWARD_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIL_UI_BATTLE_MAIL, "邮件界面战斗邮件红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_BATTLE_MAIL_NUM);
    redDotInfo.AddRedDotUnit(RedDotUnit.BATTLE_MAIL_REWARD_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.MAIL_UI_OTHER_MAIL, "邮件界面其他邮件红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.NEW_OTHER_MAIL_NUM);
}

/// <summary>
/// 初始化装备界面红点信息
/// </summary>
private void InitEquipUIRedDotInfo()
{
    RedDotInfo redDotInfo;
    redDotInfo = AddRedDotInfo(RedDotNames.EQUIP_UI_WEARABLE, "装备界面可穿戴红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.WEARABLE_EQUIP_NUM);

    redDotInfo = AddRedDotInfo(RedDotNames.EQUIP_UI_UPGRADABLE, "装备界面可升级红点");
    redDotInfo.AddRedDotUnit(RedDotUnit.UPGRADEABLE_EQUIP_NUM);
}

******

  • 上层逻辑代码只关心红点的初始化，绑定和取消

    MainUI.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/// <summary>
/// 绑定所有红点名
/// </summary>
private void BindAllRedDotNames()
{
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_MENU, OnRedDotRefresh);
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_MAIL, OnRedDotRefresh);
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_MENU_BACKPACK, OnRedDotRefresh);
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_MENU_EQUIP, OnRedDotRefresh);
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_NEW_FUNC1, OnRedDotRefresh);
    RedDotManager.Singleton.BindRedDotName(RedDotNames.MAIN_UI_NEW_FUNC2, OnRedDotRefresh);
}

/// <summary>
/// 响应红点刷新
/// </summary>
/// <param name="redDotName"></param>
/// <param name="result"></param>
/// <param name="redDotType"></param>
private void OnRedDotRefresh(string redDotName, int result, RedDotType redDotType)
{
    var resultText = RedDotUtilities.GetRedDotResultText(result, redDotType);
    if (string.Equals(redDotName, RedDotNames.MAIN_UI_MENU))
    {
        MenuRedDot.SetActive(result > 0);
        MenuRedDot.SetRedDotTxt(resultText);
    }
    else if (string.Equals(redDotName, RedDotNames.MAIN_UI_MAIL))
    {
        MailRedDot.SetActive(result > 0);
        MailRedDot.SetRedDotTxt(resultText);
    }
    else if (string.Equals(redDotName, RedDotNames.MAIN_UI_MENU_BACKPACK))
    {
        BackpackRedDot.SetActive(result > 0);
        BackpackRedDot.SetRedDotTxt(resultText);
    }
    else if (string.Equals(redDotName, RedDotNames.MAIN_UI_MENU_EQUIP))
    {
        EquipRedDot.SetActive(result > 0);
        EquipRedDot.SetRedDotTxt(resultText);
    }
    else if (string.Equals(redDotName, RedDotNames.MAIN_UI_NEW_FUNC1))
    {
        DynamicFunc1RedDot.SetActive(result > 0);
        DynamicFunc1RedDot.SetRedDotTxt(resultText);
    }
    else if (string.Equals(redDotName, RedDotNames.MAIN_UI_NEW_FUNC2))
    {
        DynamicFunc2RedDot.SetActive(result > 0);
        DynamicFunc2RedDot.SetRedDotTxt(resultText);
    }
}

    /// <summary>
    /// 解绑所有红点名
    /// </summary>
    private void UnbindAllRedDotNames()
    {
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_MENU, OnRedDotRefresh);
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_MAIL, OnRedDotRefresh);
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_MENU_BACKPACK, OnRedDotRefresh);
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_MENU_EQUIP, OnRedDotRefresh);
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_NEW_FUNC1, OnRedDotRefresh);
        RedDotManager.Singleton.UnbindRedDotName(RedDotNames.MAIN_UI_NEW_FUNC2, OnRedDotRefresh);
    }

/// <summary>
/// 刷新红点显示
/// </summary>
private void RefreshRedDotView()
{
    (int result, RedDotType redDotType) redDotNameResult;
    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_MENU);
    OnRedDotRefresh(RedDotNames.MAIN_UI_MENU, redDotNameResult.result, redDotNameResult.redDotType);

    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_MAIL);
    OnRedDotRefresh(RedDotNames.MAIN_UI_MAIL, redDotNameResult.result, redDotNameResult.redDotType);

    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_MENU_BACKPACK);
    OnRedDotRefresh(RedDotNames.MAIN_UI_MENU_BACKPACK, redDotNameResult.result, redDotNameResult.redDotType);

    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_MENU_EQUIP);
    OnRedDotRefresh(RedDotNames.MAIN_UI_MENU_EQUIP, redDotNameResult.result, redDotNameResult.redDotType);

    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_NEW_FUNC1);
    OnRedDotRefresh(RedDotNames.MAIN_UI_NEW_FUNC1, redDotNameResult.result, redDotNameResult.redDotType);

    redDotNameResult = RedDotManager.Singleton.GetRedDotNameResult(RedDotNames.MAIN_UI_NEW_FUNC2);
    OnRedDotRefresh(RedDotNames.MAIN_UI_NEW_FUNC2, redDotNameResult.result, redDotNameResult.redDotType);
}

有了这一套红点系统，上层逻辑定义红点主要由以下几个步骤组成:

  1. 定义红点名并初始化
  2. 定义红点名的红点运算单元组成并初始化
  3. 上层逻辑编写新红点运算单元的逻辑计算回调
  4. 上层逻辑绑定红点名刷新
  5. 上层逻辑触发红点名或红点运算单元标脏后，等待红点系统统一触发计算并回调

重点知识

  1. 前缀树用于实现字符串命名定义父子关系(仅仅只是调试信息上复制层级查看的父子关系)
  2. 红点名和红点运算单元通过组合的方式可以实现高度的自由组装(没有严格意义上的父子关系)
  3. 红点数据的标脏既可以基于红点运算单元也可以基于红点名，从而支持上层逻辑的准确标脏机制
  4. 如果没法在进游戏一个准确的实际出发红点运算单元全部计算，可以考虑每一个红点运算单元都通过对应模块触发标脏的方式触发计算
  5. 动态红点(比如背包不定数量道具的列表内红点)不再这套红点系统范围内定义，由上层逻辑自行触发计算和显示

Reference

Trie

Github

RedDotSystem

文章目錄
  1. 1. 前言
  2. 2. 红点系统
    1. 2.1. 红点系统需求
    2. 2.2. 红点系统设计
    3. 2.3. 前缀树
      1. 2.3.1. 前缀树实战
    4. 2.4. 红点系统实战
      1. 2.4.1. 红点系统类说明
      2. 2.4.2. 实战
  3. 3. 重点知识
  4. 4. Reference
  5. 5. Github