模拟城市交通系统
61011217
朱庆明
1、申请题目：模拟城市交通系统
模拟城市交通系统的组成部分为：小车、人、建筑物、道路。其中小车为主体，在这样一个环境中，小车可以主动寻找最优路径，司机的任务仅仅是设定一个起点和终点即可，同时，小车还会遵循各种交通规则，以及预防交通事故的发生。
2、课题背景：
1.交通安全至关重要，目前交通事故频发，根据这个现状可以有一个设想，如果交通系统可以只由机器控制，完全自动化，发生交通事故的几率就会大大减小，模拟和现实固然差距很大，所以这个模拟设计只是作为实际的一种设想。
2.社会发展的一个基本目标是解放生产力，研制这样一种交通工具就可以解放司机这一生产力，同时，不需要学驾驶，人人都会开车，只要设置起点和终点即可。
3、项目规划：
一. 功能（核心功能：实现指针算法）：
1. 开关控制状态机；
2. Vga动态显示（1024x768分辨率，一张静态背景图和6个动态图层）；
3. 键盘按键设定起点和终点（两次按键形成一个数据，且不会出现中间变量，即第一次按键完成时不会产生影响）
4. 小车可以从起点找到一条路径行驶到终点并停下（这条路径通常是最短路径）；
5. 小车行驶过程中可以随时切换速度为高速或低速行驶；
6. 小车行驶过程中可以人为使其暂停；
7. 整个城市交通系统的交通路口处的红绿灯及倒计时的控制；
8. 小车在遇到交通路口处遵循红灯停，绿灯行的交通规则；
9. 小车在交通路口右转时即使红灯也可以通过；
10. 键盘按键控制人的移动，上下左右运动及暂停；
11. 小车观察到附近有人时会急停，避免发生交通事故；
12. 开发板上LED灯显示交通路灯变化情况及到达终点的标志；
二. 操作流程及显示
1.开关及键盘的功能：
Switch0（以开发板上标注的名称为准）：1-设置起点；0-设置终点
Switch1 ：1-小车行驶；0-小车暂停
Switch2 ：1-小车正常速度行驶；0-小车低速行驶
Switch3 ：1-人行驶；0-人暂停
各状态之间的关系：
键盘分时复用，当人行走时（Switch3=1），键盘用来控制人的行动（2-上，5-下，4-左，6-右），当人暂停且小车不在行驶中时（Switch1=0 and Switch3=0），键盘才可以被用来设置起点和终点位置（键盘连续输入两个数字，从00到15（十六进制），共22座建筑物可供选择）。即Switch1、Switch2、Switch3之间互不干扰，但是Switch0的功能受Switch1和Switch3的限制。
2.操作流程
开始时所有开关均为0，将Switch0拨到高，键盘按键输入选择起点，再拨到低，选择终点（或者倒过来，随意），然后将Switch1拨到高，观察小车行驶。不论在什么时候，都可以通过设置Switch2的状态来设置小车的速度模式；在小车行驶的任意时刻，也都可以改变Switch1的状态来让小车暂停或继续行驶。不论在什么时候（除了设置起点和终点的时候），都可以通过设置Switch3的状态来控制小人的运动，但是只要Switch3为1，键盘就只能被用来控制小人的移动。
3.显示
蓝色线条为道路，矩形为建筑物，也是可以被设置为起点或终点的地方（设为起点的矩形为红色，设为终点的矩形为绿色，其他矩形为粉红色），较大的绿色矩形为小车，天蓝色的圆形是小人，在地图下方一片区域显示交通灯及交通路口倒计时的数字。
三. 输入输出接口（见系统结构）
4、实现方案：
由于实现的功能很多，这里指介绍核心功能——指针算法及其实现，想要详细了解所有功能可参阅源代码。
寻找最短路径的算法早已有之，典型的如Dijkstra算法、Johnson算法，但是在面对城市交通系统这一实际问题时，我发现这些算法的实用性有严重缺陷，关键在于，这些经典算法的实现都需要一个前提条件：已知地图上任意两点间的距离。若地图上有n个点，则需要知道的距离数是，很容易看出这样一个算法的复杂度是以阶的，如果n足够大，则算法的复杂度不可想象。对于大中型城市来说，n足够大是必然的。其实不仅仅是运算速率的问题，因为我们是想用硬件电路来寻求最短路径，因此需要存储这些距离，这样一个算法的空间复杂度亦为阶，如果n足够大，为了存储这些距离所占用的硬件资源也是不可想象的。
如果我们再回到城市交通系统这样一个实际问题中，就会发现这些经典算法还有更大的弊端，这么多的距离从何而来？我们必须先调查清楚哪些路径点之间是可通行的，其次，对于所有可通行的两路径点，我们需要依次测量其距离，人力、物力、财力的耗费……并且如果地图中任一点的位置有了变动，或者增加了某个新的路径点，一部分数据又要重新测量确定。
综上所述，我认为经典的最短路径算法不适用于我所研究的课题。经典不是万能的，在遇到具体的实际问题中，我们要有所创新，打破经典。
为了迎合城市交通系统这样一个环境，我思索出了一种新的算法，由于最初的idea是从指南针得来，我称为指针算法，其算法的复杂度是常数阶，与经典的最短路径算法的阶复杂度相比有无可比拟的优势。此算法的思路很简单，所以可能早已被别人发现并运用起来，不过我是独立创作的。
指针算法的思路：假设车里有一个指针，始终指向目标地点，我们就沿着指针的方向走就肯定可以到达目的地。
指针算法的实现：首先，车在道路上不可以随意转向，只能沿着路走，因此，只要车在一段路上，算法就可以暂停；只有当车走到道路交叉点，即路口时才需要判别走哪条路最合适，比较的对象最多只有三个，即继续向前、向左或向右，假设这三个方向的方向向量分别为v1，v2，v3，此时再计算一个向量v，其方向从车的当前位置指向目的地，用v分别与v1，v2，v3做内积，和v内积的值最大的那个方向一定是和目的地方向最接近的。只要在每个道路交叉作最多三次内积运算和比较运算，最后就可以到达目的地。
指针算法与经典算法的比较：
1.性能：经典算法是事先确定路线，使用者需要等待算法计算完成，路径确定完全才开始行驶；指针算法在行驶之前不需要任何操作，路径是实时确定，只需要在每个路口作最多三次内积运算和比较运算，无论这个交通系统有多复杂，这样一种运算所耗费的时间都是固定且可以完全忽略的。行驶前不需要运算，行驶时运算所用的时间固定且可以完全忽略，因此可以认为指针的性能是无穷高。
2.资源占用：指针算法不需要知道路径点之间的距离，只需要知道地图上各路径点的位置坐标，这样一种存储是n阶的，当然也是必不可少的；经典算法不仅要知道地图上各路径点的位置坐标，还要知道其中任意两点之间的距离，存储是阶的。
如果说算法的好坏只取决于其时间和空间复杂度，那么与指针算法相比，流传数百年的经典算法似乎已经是一无是处，但其实远不是这样，有一点指针算法无法与经典算法相比：一个算法最基本的评判标准是是否实现了预期的功能，经典算法一定可以找到最短路径，指针算法一定可以找到路径，但这个路径不一定是最短路径。
由于指针算法我已经用软件实现，所以下面我截图来说明指针算法找到的不一定是最短路径。
如下图所示，此应用程序还有制作地图的功能，首先是用其制作一张地图，其中黄色线条是道路，紫色矩形是建筑物，红色圆圈是道路交叉口；我们现在只要选择一个建筑物作为起点，另一个建筑物作为终点，按下开始就可以观察小车的行驶了，为了明显看出小车走的不是最短路径，我们选择其中特殊的两个建筑物，如第二幅图所示（部分截图）：
其中有一个紫色矩形变为绿色，表示起点，一个矩形变为红色，表示终点，道路上出现一个蓝色矩形，表示小车，小车出现在起点处。很容易地，我们可以看出最短路径中小车初始应该向右走，但是如果我们用指针算法来对初始位置进行判别，得出的是小车向左走，实际截图如下：
如果我们继续使用指针算法，或让小车继续走，可以看出其还是可以到达终点，但是很明显走的不是最短路径了。
经过上述，可以小结一下，指针算法唯一美中不足的地方是其不可以很好的完成搜索最短路径的功能。但是，我想说，在城市交通系统这样一个特定的环境中，我们可以认为指针算法是完美的，其行走的路径就是最短路径。这样的观点看似没有道理，其实只要n足够大，这个观点就成立。
如果n足够大，意味着道路的交叉口就足够多，每个路口的计算量不变，因此算法性能保持不变，但是由于判别的机会更多了，判别失误的几率也就更小了，或者说下一次的判别可以很好地抵消上一次判别失误的影响。如果n趋向无穷大，判别次数就无穷多，我们思索一下就会发现，这时候指针算法找到的是最短路径的可能性其实很小，因为路径数量太多了，但是，其和真正的最短路径的总长度差值会近似为0，工程上讲究的是实用，我们完全可以认为这就是最短路径。下面依然图示说明一下其中的道理：
如果n增大了，地图变成了下面这个样子，那么尽管一开始小车向左走是不对的，但很快它就有了一次判别转向的机会，最后其行驶路径还是最短的或者可以看成是最短的。
总结一下，在城市交通系统这样一个特定环境中，指针算法的优越性完全超过了经典算法，指针算法的性能近似为无穷高，而经典算法的时间复杂度却是阶；指针算法的空间复杂度为n阶，经典算法的空间复杂度为阶；如果n不断增大，经典算法耗用的时间和占用的资源都飞速增长，对于通常的算法来说也都是这样，算法规模增大了，时间空间复杂度都是增加的，可对于指针算法来说，时间复杂度保持不变，即性能依旧可看作无穷高，空间复杂度只是n阶变化，并且n越大，找到最短路径的概率反而越大，算法规模增大对于指针算法产生的是积极影响。
5、系统结构：
1.顶层模块的RTL综合图（由于顶层模块也是用代码编写的，因此只能贴出其RTL综合图，如果觉得此图不够清晰，在源代码压缩文件中也存放了此图的原图）：
2.管脚绑定
|
信号名称
|
管脚
|
备注
|
|
Col[0]
|
H8
|
Col(0)
|
|
Col[1]
|
J7
|
Col(1)
|
|
Col[2]
|
K8
|
Col(2)
|
|
Col[3]
|
K7
|
Col(3)
|
|
Row[0]
|
E4
|
Row(0)
|
|
Row[1]
|
F3
|
Row(1)
|
|
Row[2]
|
G8
|
Row(2)
|
|
Row[3]
|
G7
|
Row(3)
|
|
ICLK
|
D11
|
100M晶振
|
|
SwitchB
|
V5
|
Switch<0>
|
|
SwitchG
|
U4
|
Switch<1>
|
|
SwitchF
|
V3
|
Switch<2>
|
|
SwitchH
|
P4
|
Switch<3>
|
|
Red[0]
|
B2
|
Vga.R
|
|
Red[1]
|
H3
|
Vga.R
|
|
Red[2]
|
H4
|
Vga.R
|
|
Green[0]
|
M6
|
Vga.G
|
|
Green[1]
|
H6
|
Vga.G
|
|
Green[2]
|
N6
|
Vga.G
|
|
Blue[0]
|
N7
|
Vga.B
|
|
Blue[1]
|
P7
|
Vga.B
|
|
VSYNC
|
V18
|
Vga.场同步信号
|
|
HSYNC
|
V17
|
Vga.行同步信号
|
|
Over
|
W3
|
LED<0>
|
|
LRed
|
T8
|
LDT2-R(LD11)
|
|
LGreen
|
R7
|
LDT2-G(LD9)
|
6、状态流程图：
1.指针算法流程图：
2.状态图：
7、各主要模块仿真结果波形
无。根据我使用FPGA的实际经验来看，仿真，或者说ISE自带的仿真仅仅适用于简单的系统设计，对于大型的或复杂的系统设计没有太大帮助，养成良好的设计习惯，遵循严格的语法要求，才是ISE硬件调试最大的助手。
8、课程设计总结
1.发挥部分：加入车流，模拟更真实的城市环境；设置更多的交通规则并完成等。
2.收获与体会：
1) 经过这学期数字系统的学习和实践，使我对FPGA、对ISE、对VHDL有了更加深刻的了解，对如何驾驭VHDL，如何进行硬件调试、如何解决时序问题、如何设计出一个更加稳定可靠的系统有了更深的了解与更多的经验。可以将这看成是数字电路学习的一个良好开端。
2) 通过这次的数字系统学习再次证明了我的创新能力，不过原则上来说创造算法还是与软件关联比较密切，实际上用硬件来实现指针算法是一项耗时耗力耗资源且难以发挥最佳效果的做法，从实用性来说没有任何意义，只能当成是强化数字电路的学习。
3) 之所以能够完成这次的数字系统训练，其实很大程序上是因为我制作了相应的软件来进行助攻，所有rom的编写、原始数据的初步分析、指针算法的调试与成熟，全都是由软件来完成，硬件只是利用了软件数据分析的结果，仿照软件实现指针算法的方法重新实现了一遍，在功能上远远无法与软件实现的功能相比。这也说明今后的很多系统设计不应该用纯硬件来实现，应该遵循软件是主体，硬件是提高性能的关键这一原则来进行系统设计。
3. ISE硬件系统设计经验
1. 能用组合逻辑实现的功能坚决不用时序逻辑来实现；
2. 只能用时序逻辑来实现的功能通常可以拆分组合逻辑和简单的时序逻辑来实现，最简单的时序逻辑就是触发器，当然计数器也是经常要用的；
3. 综合前两点，我认为任何一个复杂的系统设计最后都可以归结为一堆复杂的组合逻辑和一些很简单的时序逻辑，只要系统的设计者愿意去花心思，这样系统才会足够稳定，调试也会变得非常简单，系统才能做得更大更复杂，实现更多更强的功能；
4. 组合逻辑设计：之所以要用组合逻辑来实现复杂功能就是因为组合逻辑不会带来时序问题，但这个前提是正确使用了组合逻辑，如果写了这样的组合逻辑语句：
A <= ‘1’ when B = ‘1’ else A;
看似这是组合逻辑，而且可以通过编译，但实际上一看warning就知道生成了latch锁存器，一定带来了时序问题。我们应该有一个基本常识，组合逻辑一定不能存储信号。
5. 时序逻辑设计：前面提到了，我们需要而且可以将复杂的时序逻辑变成复杂的组合逻辑和简单的时序逻辑，就是用触发器和计数器来实现，但是，即使只用了触发器和计数器来实现，依然可能会出问题。我们可以将时序逻辑再划分为同步和异步两种逻辑，我的建议是，可以用同步逻辑实现的地方不要用异步逻辑来实现，显然，异步逻辑更有可能带来竞争与冒险。
6. 时序逻辑设计：即使上面说到的都做好了，还是可能会出现时序问题，因为前面所说的都是一些良好习惯，竞争与冒险需要根据实际的具体情况来解决。这就需要设计者对自己设计的时序足够了解。只要找到了竞争与冒险的根源，就很好解决了，我的习惯通常都是用时钟延时来解决。
7. 一个近似是万能的系统设计方法，在ISE的第一步语法分析完成后就可以看到所有的warning，如果其中提到了生成了latch或者有可能生成latch，则一定会有时序问题，而且这些时序问题很可能有部分是隐藏的，这就是为什么上学期和这学期困扰了大家ISE设计的一个主要原因，大家都觉得出来的结果和设计的预想不一样，而且略做改动结果就变化了很多，甚至是与改动毫无关联的地方，我们可以认为所有的地方都有latch，都有问题，只是latch有时候隐藏自己，所以我们以为某个功能做好了，但是略做无关的改动又错了，这是latch又露面了（我的猜想~）。因此，只要我们可以使得warning中没有latch，甚至没有waring，那么时序问题就会减少很多很多。但也不是完全没有，如果设计者原有的设计中就存在着竞争与冒险，是设计者自己没发现，那就不能怪ISE不稳定了，只能说如果没有latch，ISE不会误解设计者的意图。如何消除所有的latch，方法是：养成良好的编程习惯，严格遵循标准语法的要求，使用更加简单的时序逻辑。
8.针对第7点做一个补充，latch本身也是一个器件，所以如果大家很清楚latch的时序，并且有一定的使用经验，完全可以忽略第7点，用latch和触发器共同进行时序逻辑的设计，latch不是害群之马，只是需要正确地使用。
9、参考文献
无