Welcome to my blog. You can post whatever you like!
The blog post is using markdown, and here is a simple guide. Markdown Guide
LOGIN TO POST A BLOG
Author: Satori
Posted: 2017-06-29 18:11:16
Category:
AI
LYNE
技术
游戏
Views: 1090
Comments: 0
最近steam夏季打折,不得不剁手233,在推荐里面看到了一款叫LYNE的小游戏,很符合我的风格233
[LYNE 游戏steam地址][1]
![LYNE][2]
这个游戏规则很简单,就是类似一笔画把所有的相同图案一笔画画完。
比如上图就有3个不同的图案,三角形、菱形和正方形。其中每个图形有两个特别的图案,分别对应这个图案的起点和终点。对于每种图形而言,从起点出发,画出一条路径把这种图形全部串进来,最后走向终点。一共有8个方向可以走(**不越界**的情况下),然后所有画出的路径不能交叉。当从一个起点出发的时候一路上只能走相同的图形,不能去其他的图形。
其中这游戏难点在于除了基本图案之外还有一个正八边形的特殊图形,它可以起到一个桥梁的作用,任何图形都能走到它那里,不过从这个图形出来的图形必须是另一个正八边形或者和起点相同的图案,它中间有孔,孔的个数代表需要从其它图形走到它那里几次(也就是**入度**),走多走少都不行。
但是这个游戏不好的一点是关卡太多,一共26个大关,每一个大关有25个小关,一共650关,打起来相当费劲,到后期难度非常大,非常耗时,很多时候需要试,打玩3个大关的时候,我就已经不行了QAQ
其实这个游戏最难的地方还是在于正八边形,它最灵活,任意图形都能到它,导致出现很多种可能性。游戏后期大量出现孔很多的正八边形,给游戏带来许多困难。
### **所以我机智地写了一个AI去解决这个问题**
整体的思路是基于递归回溯,步骤如下。
- 先选一个没有走过的起点
- 从起点出发,寻找正八边形或者同形状的图形
- 判断某个方向走是否会发生边的碰撞
- 新到的点是否为终点,如果是换一个起点
- 如果所有起点走完了,就看看所有的图形和正八边形是否走完或者走全了,是就返回结果,不是就回溯。
### 具体到代码,主要用以下几个数据结构:
- map: 用于存原始棋盘的信息,用数字代表图形的种类,特别的,0代表正八边形
- end_point: 用于存储不同种类图形的起点和终点
- need_visit: 用于存某个点需要走过的个数(普通图形为1,正八边形为孔的个数,当所有点数值为0时认为遍历成功)
- link: 用于存储哪些点相连,用于边的碰撞检测
- res: 用于存走过点的顺序集合,也就是最终的结果
### 具体的代码如下:
```
#include <vector>
#include <string>
#include <fstream>
using namespace std;
typedef pair<int, int> Point;
// The max size of the map
int const MAX = 10;
int row, col;
// map: the map of original map, number start from 1 represents different type, 0 represent general point
int map[MAX][MAX];
// end_point: the map of end point, number start from 1 represents the end point, 0 represent non endpoint
int end_point[MAX][MAX];
// need_visit: the count of times that the point should be visited
int need_visit[MAX][MAX];
// link: the collection of connected points
vector<pair<Point, Point>> link;
// res: the result of the route
vector<Point> res;
// final_res: the partitioned result
vector<vector<Point>> final_res;
void init()
{
// initial array
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
map[i][j] = -1;
end_point[i][j] = 0;
need_visit[i][j] = 0;
}
}
ifstream in("in.txt");
in >> row;
in >> col;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
char ch;
in >> ch;
// normal point
if (ch >= 'a' && ch <= 'z')
{
map[i][j] = ch - 'a' + 1;
need_visit[i][j] = 1;
}
// general point
else if (ch >= '0' && ch <= '9')
{
map[i][j] = 0;
need_visit[i][j] = ch - '0';
}
// end point
else if (ch >= 'A' && ch <= 'Z')
{
map[i][j] = ch - 'A' + 1;
end_point[i][j] = ch - 'A' + 1;
need_visit[i][j] = 1;
}
}
}
in.close();
}
Point findEndPoint()
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
// if it is a end point that is not visited
if (end_point[i][j] != 0 && need_visit[i][j] > 0)
{
return Point(i, j);
}
}
}
return Point(-1, -1);
}
bool judgeAllVisited()
{
// judge if all point is visited
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
// if a point is not visited
if (need_visit[i][j] != 0)
{
return false;
}
}
}
return true;
}
bool isInBoundary(int r, int c)
{
return r >= 0 && r < row && c >= 0 && c < col && map[r][c] >= 0;
}
bool isSameType(Point &cur, Point &next, int cur_type)
{
if (map[cur.first][cur.second] == map[next.first][next.second])
{
return true;
}
// if next is a general point
if (map[next.first][next.second] == 0)
{
return true;
}
// if next point follows the same pattern
if (map[cur.first][cur.second] == 0 && map[next.first][next.second] == cur_type)
{
return true;
}
return false;
}
bool isEdgeConfilct(Point &a, Point &b)
{
for (pair<Point, Point> &p : link)
{
// if the edge has already existed
if (p.first == a && p.second == b || p.first == b && p.second == a)
{
return true;
}
// if the cross edge existed
Point c(a.first, b.second), d(b.first, a.second);
if (p.first == c && p.second == d || p.first == d && p.second == c)
{
return true;
}
}
return false;
}
bool isEndPoint(Point &p)
{
if (isInBoundary(p.first, p.second))
{
return end_point[p.first][p.second] > 0;
}
return false;
}
bool find(Point cur_point, int cur_type, bool is_begin = false)
{
// if ends with an terminate point
if (isEndPoint(cur_point) && !is_begin)
{
return find(Point(-1, -1), -1);
}
// if no terminate point is selected, then select one
if (cur_point.first == -1 && cur_point.second == -1)
{
cur_point = findEndPoint();
// if no terminate point is found
if (cur_point.first == -1 && cur_point.second == -1)
{
// if all visited, solution found, else backtrace
return judgeAllVisited();
}
// if find a end point
else
{
res.push_back(cur_point);
need_visit[cur_point.first][cur_point.second]--;
if (find(cur_point, map[cur_point.first][cur_point.second], true))
{
return true;
}
// if there's no solution on current situation, recover the state
else
{
res.pop_back();
need_visit[cur_point.first][cur_point.second]++;
return false;
}
}
}
// select the current point
int cur_row = cur_point.first;
int cur_col = cur_point.second;
// choose from eight directions
for (int offset_row = -1; offset_row <= 1; offset_row++)
{
for (int offset_col = -1; offset_col <= 1; offset_col++)
{
int next_row = cur_row + offset_row;
int next_col = cur_col + offset_col;
// next point is not the current point and the next point not exceed boundary
if (!(offset_row == 0 && offset_col == 0) && isInBoundary(next_row, next_col))
{
Point next_point = Point(next_row, next_col);
// if next point is of same type and is not visited
if (need_visit[next_row][next_col] > 0 && isSameType(cur_point, next_point, cur_type))
{
// if the edge is not conflict
if (!isEdgeConfilct(cur_point, next_point))
{
link.push_back(pair<Point, Point>(cur_point, next_point));
res.push_back(next_point);
need_visit[next_point.first][next_point.second]--;
// test next step
if (find(next_point, cur_type))
{
return true;
}
// if next step fails
else
{
link.pop_back();
res.pop_back();
need_visit[next_point.first][next_point.second]++;
}
}
}
}
}
}
// if all directions fail
return false;
}
void foramat_result()
{
vector<Point> tmp;
bool is_startp = true;
for (int i = 0; i < (int)res.size(); i++)
{
tmp.push_back(res[i]);
if (end_point[res[i].first][res[i].second])
{
if (!is_startp)
{
final_res.push_back(tmp);
tmp.clear();
}
is_startp ^= 1;
}
}
}
void output()
{
ofstream os("out.txt");
for (vector<Point> &vec : final_res)
{
os << '(' << vec[0].first + 1 << ", " << vec[0].second + 1 << ')' << endl;
for (int i = 0; i < (int)vec.size() - 1; i++)
{
int cur_row = vec[i].first, cur_col = vec[i].second;
int next_row = vec[i + 1].first, next_col = vec[i + 1].second;
int r = next_row - cur_row + 1, c = next_col - cur_col + 1;
string symbol[3][3] = { "↖", "↑", "↗", "←", "", "→", "↙", "↓", "↘"};
os << symbol[r][c] << " ";
}
os << endl;
}
os.close();
}
int main(void)
{
init();
find(Point(-1, -1), -1, true);
foramat_result();
output();
return 0;
}
```
写代码的时候主要遇到两个问题。
第一个是判断起点终点问题。当一个图形遍历完后要开始下一个图形的遍历,我在调用函数时把当前结点改为非法结点来判断是否需要重新分配起点,但是后面马上有一个逻辑判断是否到了终点,到了就重新分配起点。问题就在这里,在逻辑上起点和终点是等价的,可以交换的,从起点到终点和从终点到起点是等效的,当分配一个起点的时候,递归进入下一层的时候马上就会判定到了终点,然后又重新分配起点。
所以解决方法就是强行在递归调用的时候加一个标签判断是否是新分配的结点。如果是新分配的结点就不当成终点,也就不再分配起点了。
第二个是判断同类型图形的问题。这个问题主要发生在正八边形的时候。对于正八边形而言,所有到它的结点都能成立,但是从正八边形出来的图形就不一定了,从正八边形出来的图形必须和起点的图形相匹配,因此递归调用的时候需要知道当前序列的起点是哪种类型的图形,根据这个判断从正八边形出来的图形到底是那个。
总之花了大概半天的时间写出来了,还是比较高兴的。主要是可以拿全成就,有A-Z一共26个成就,感觉还是不错的233.
### 代码的使用方法
1. 编译源代码
2. 编写输入文件,文件命名为`in.txt`
文件编写规则:
第一行, 写行数和列数,用空格隔开
从第二行起,为每个图形编写符号,符号之间用空格隔开,编写符号及规则如下:
3. 运行程序,得到out.txt
|图形|表示方法|备注|
|:-----:|:------:|:------:|
|空|?|如果某一格没有图形,用问号表示|
|一般图形|小写字母a到z|一般图形,如三角形、正方形、菱形|
|端点图形|大写字母A到Z|相同的图形大写字母和小写字母匹配|
|正八边形|数字2到4|正八边形有几个孔就是几|
示例:
```
4 3
? A B
c C 2
C 3 2
B c A
```
意思是棋盘有4行3列, 第一行第一列没有图形,第一行第二列和第四行第三列是同一个图形,而且都是端点。第一行第三列和第四行第一列是另外一种图形,而且都是端点,第二行第一列第二列、第三行第一列、第四行第二列又是另外一种图形,其中第二行第二列和第三行第一列是端点。最后第二行第三列和第三行第二列和第三行第三列是数字,分别代表有2、3、2个孔的正八边形。
最后根据out.txt来得到走的序列路径。
[1]: https://store.steampowered.com/app/266010/LYNE/
[2]: https://lh4.ggpht.com/bdr5fWHTqNBz26TMe6Eyuh1jou-Qt2QpH92PT-ERz3I5i01DXZgzo9WV2q2g5nt8XA=h900
Read More
Author: Satori
Posted: 2017-06-18 00:50:45
Category:
https
心得
技术
Views: 3752
Comments: 0
最近想给网站安上证书,这样就能加上https支持。经过各种查资料过后,最后使用letsencrypt免费认证,不得不说人家真的是良心CA,真的是不给钱,而且安装特别方便,它有一个客户端[certbot][1]能很方便的通过几条简单的命令就能直接安装证书,适配nginx等等,可以说一键就能添加https支持。
在给网站装证书的时候,到安装证书这一步的时候,遇到了一个报错信息,如下:
> Failed authorization procedure. chongliu.me (tls-sni-01): urn:acme:error:connection :: The server could not connect to the client to verify the domain :: Error getting validation data, www.chongliu.me (tls-sni-01): urn:acme:error:connection :: The server could not connect to the client to verify the domain :: Error getting validation data
然后报错信息下面给出了疑似的解决方法:
> - The following errors were reported by the server:
Domain: chongliu.me
Type: connection
Detail: Error getting validation data
Domain: www.chongliu.me
Type: connection
Detail: Error getting validation data
To fix these errors, please make sure that your domain name was
entered correctly and the DNS A record(s) for that domain
contain(s) the right IP address. Additionally, please check that
your computer has a publicly routable IP address and that no
firewalls are preventing the server from communicating with the
client. If you're using the webroot plugin, you should also verify
that you are serving files from the webroot path you provided.
但是这个报错信息怎么看都和我的情况不符。我的vps既有公网ip,也有域名,而且通过域名能够访问我的网站。所以问题肯定不在这里。我无奈之下看了一下它的[官方使用手册][2],从手册中的得到证书部分发现了它要占用443端口。我突然想起了什么事情。我的**科学上网**的ss服务器似乎用的是443端口。抱着试一试的心态我关掉了ss服务。结果瞬间成功。
另外比较6的一点是这个客户端很强大,能自动识别你绑定的域名,以及让你选择是所有的链接都走https还是既可以走http还是https,比较人性化。
不过有一个要自己关心的问题是它证书每90天会过期,因此需要写一个cron job来每60天更新一下证书。另外还有一个小问题是我需要让ss换一个端口,不然下次证书又得不到。
总之这次的收获还是遇到问题要多看一下官方文档,看看它大概的实现方法,这样说不定就能找到问题所在。比如这次我看了端口占用情况才想到端口冲突问题。官方文档虽然大多数时候我们并不想看,但是它才是真正最权威的文档233
[1]: https://certbot.eff.org/
[2]: https://certbot.eff.org/docs/using.html#getting-certificates-and-choosing-plugins
Read More
Author: Satori
Posted: 2017-06-14 23:39:27
Category:
sorrow
Views: 645
Comments: 0
[This article][1] written by my ex girlfriend covers some stories about our pasts.
Even one year passes, I still cannot recover from a sense of guilty for what I have done to her. I don't dare to read word by word until my tears went fully dry. I decided to read it near the Jimen bridge where she lived before when the sky goes dark, with stars shining on the sky and moonlight reflects on my face.
I think I **should definitely** write something about my past too, to see how many foolish things I did and how deep it hurt my ex girlfriend. Then, I should find what I did wrong and how I can handle these things properly.
Although we don't keep in touch anymore, but I still appreciate for her guidance and patience.
I will compose an article as soon as possible.
[1]: https://mp.weixin.qq.com/s/b4B6HKRhvk0no4TNiQnCyA
Read More
Author: Satori
Posted: 2017-06-07 08:38:44
Category:
日常
Views: 707
Comments: 0
昨天早上照毕业照,结果下大雨,直接被淋爽,然后晚上不太舒服,只能提前睡觉。今天6点半就醒了,然而手机掉到床底下,然后早上找了好一会儿,最后找到已经7点10分了,再下去扫车发现手机没电了,然后又上去拿充电宝。充一会儿电继续扫,结果扫描二维码耗电太多,结果直接关机。最后不得不去坐公交车。到地铁站发现没钱了,手机没电充不了,还需要去充值。最后赶到公司已经晚了10分钟。
真的是福无双至,祸不单行。
心累QAQ
Read More
Author: Satori
Posted: 2017-06-03 21:49:59
Category:
测试
Views: 768
Comments: 0
![神尾观铃1][1]
地址: [https://chongliu.me/media/user_1/1.jpg][2]
[1]: https://chongliu.me/media/user_1/1.jpg
[2]: https://chongliu.me/media/user_1/1.jpg
Read More
Author: Satori
Posted: 2017-05-31 00:49:06
Category:
坑
Views: 823
Comments: 38
- 增加上传图片功能,做成网盘的形式,能增删改
- 修复post页面书写框覆盖问题
Read More
Author: Satori
Posted: 2017-05-20 16:44:43
Category:
进度追踪
Views: 723
Comments: 5
论文写完了,结果前言以及相关技术抄的太多了直接拉高了重复率,真心心累,需要进行refactor一下了。
paperpass一共提供了21页的查重报告,这里记录有多少已经完成。
![enter image description here][1]
用一张**レム**鼓励自己233.
[1]: https://ww2.sinaimg.cn/large/006fFWvGjw1f74v5uedajj30sx0i30ud.jpg
Read More
Author: Satori
Posted: 2017-05-15 00:56:01
Category:
诗
魁拔
Views: 656
Comments: 0
> 我的小鱼你醒了,
还认识早晨吗?
昨夜你曾经说,
愿夜幕永不开启。
你的香腮边轻轻滑落的,
是你的泪,还是我的泪?
初吻吻别的那个季节,
不是已经哭过了吗?
我的指尖还记忆着,
你慌乱的心跳。
温柔的体香里,
那一缕长发飘飘。
Read More
Author: Satori
Posted: 2017-05-06 14:40:32
Category:
进度追踪
Views: 777
Comments: 15
一共要到60页。记录一下自己一共写了多少。写累的时候可以自己鼓励一下自己233
Read More
Author: Satori
Posted: 2017-05-04 23:56:23
Category:
坑
Views: 734
Comments: 0
  一天写3页都累得不行,写60页感觉太困难了。
  算一下,16号要交初稿。12天要写60页,每天写5页,感觉任重而道远啊。仔细想有4天周末爆肝时间,可能需要每天写10页?然后每个晚上写3页的样子?
  关键还要画很多图,effort也很大。看来接下来的两周真的会很忙了。
  感觉真的要静下心来写毕设了。**1.2倍行间距**真的是服了,太紧了。QAQ
周末马上要来了,是时候来检验爆肝的成果了233
Read More