每个程序员都应该挑战的6个项目
作者:Austin Z. Henley
编译:码农翻身
有不少学生和专业的开发人员都想做一个业余的项目,以此来锻炼提高自己的技术能力,但是他们并不清楚要做点啥。
我给大家看下这几个让我受益匪浅的项目,每个项目都可以多做几次,每次都会让你学到新的东西。当你不知道学习什么东西的时候,不妨以这些项目作为驱动。
文本编辑器
我们每天都使用文本编辑器,但是你知道他们到底是怎么工作的吗?忽略掉那些炫酷的功能,你怎么实现一个能够支持选择,插入,删除文本,并且移动光标的文本框呢?
当然了,你不能使用那些GUI框架中已经做好的文本框组件。
最大的挑战就是弄清楚如何在内存中保存文档,我首先想到的就是数组,可是数组在插入文本的时候有着很差劲的性能。幸运的是,还有几个漂亮的数据结构来解决这个问题。
另外一个难点就是理解光标在文本编辑器中的行为,比如,当我在一个文本的*,开始按“向上”箭头的时候,光标应该向哪里移动?
在同一列移动?不,如果上面的那一行比较短,光标会移动到那一行的末尾,然后再往上移动,如果那一行文本较长,光标还会回到那一行的中间位置。
这就意味着需要记住光标所在的列,这样才有可能回来。我之前根本没有注意到这些小细节,直到我开始实现的时候。
实现了基本的编辑功能以后,下面两个更有趣的挑战是:undo/redo和单词换行。
以有效的方式来实现undo/redo让我大吃一惊,我先是尝试了用一个数组保持之前的状态,然后转向了Memento 模式,最后才使用了命令模式。 而单词换行会强迫你把文本的内存存储和视觉表现分开。
从文本编辑器能学到的东西
存储文本的数据结构:array, rope, gap buffer, piece table.
光标的行为和实现
undo/redo的设计模式
利用抽象把文本的存储和表现分开
进一步阅读:
文本编辑器的数据结构:
https://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table/
设计和实现一个Win32的文本编辑器:
http://www.catch22.net/tuts/neatpad#
《数据结构和算法:Java描述》
(码农翻身老刘乱入:我更推荐《算法》)
2D 游戏 -- 太空入侵者
即使是最简单的游戏也需要独特的数据结构和设计模式,我们是来学习的,所以最好使用一个简单的2D图形库(如SDL,SFML,PyGame),而不是一个隐藏了很多细节的大型游戏引擎。
首先,你得学会如何在屏幕上绘制东西,实际上你是在清理屏幕,然后快速连续地绘制屏幕的每个部分,一秒多次,以产生物体移动的效果。
其次,你会学会游戏循环,一个游戏实际上是在绘制,获取用户输入,处理游戏逻辑中间的有效的循环操作。
第三,你会学会如何处理用户的输入,我之前从未注意过按下,按住,释放一个按键或者鼠标的细微差别,更不用说处理双击操作了。另外你多久检查一次用户输入?如果一直检查,那游戏的其他部分就被冻结,无法工作了。
第四,你会学会如何创建和管理游戏中的对象,以及他们的状态。例如如果动态地创建一定数量的敌兵?工厂模式能帮助不少。
第五,你会学会如何应用游戏逻辑,什么时候更新子弹的位置?什么时候更多的敌兵应该在屏幕上出现,你如何得知敌人被消灭?什么时候游戏结束?我之前从未用过按模计算,现在我的游戏代码中到处都是了。
基本的游戏运行起来以后,可以增加一点屏幕菜单,游戏结束的画面,探索如何实现有点儿智能的敌兵,如果还觉得不够的话,还可以增加材质,声音,在线的多个玩家!
能学到的东西:
屏幕绘制
获取用户输入
游戏循环
创建和管理动态数量的物体
状态机
播放声音,使用材质, 网络功能
进一步阅读:
《游戏编程模式》
https://gameprogrammingpatterns.com/contents.html
《Data Structures for Game Programmers》
《Programming Game AI by Example》
我从8个视频游戏中学到的8个教训
http://web.eecs.utk.edu/~azh/blog/8lessons8games.html
编译器- Tiny BASIC
我做过的最引人注目的项目是编译器,时至今日,如果我周日的下午有空编程的话,我仍然回去写编译器。
通过创造一个东西,使得别人能创造更多东西,这种感觉实在太棒了。
通过实现一个编译器,我必须得学习很多复杂的编译器技术,这些技术通常来说根本想不到。我建议从零开始写编译器,并且从一个很小的BASIC-like的语言开始(例如Tiny BASIC,https://en.wikipedia.org/wiki/Tiny_BASIC ),然后把它编译成你所熟悉的语言。
例如,你可以用Python写一个编译器,把Tiny Basic编译为C#代码, 不需要输出成汇编,这能让你专注到编译器本身。
编译器的第一个障碍就是如何做词法分析,然后你需要构建一颗抽象语法树,递归下降是个非常漂亮的技术。
接下来做语义分析,确保代码是有意义的,规则会被遵守。最后输出目标代码。
不要被那些术语吓住,编译器有海量的资料,先让你的基本的编译器工作起来,然后增加一些标准库(如简单的2D图形功能),优化参数传递,改进错误提示。
最后,你应该用自己的语言写一些例子程序,向全世界展示你的工作成果。
可以学到的东西
词法分析
语法分析
递归下降分析
抽象语法树
语义分析
代码优化
代码生成
进一步阅读
《Crafting Interpreters》
https://www.craftinginterpreters.com/contents.html
《Write an Interpreter in Go》
《Let's Build a Compiler 》
https://compilers.iecc.com/crenshaw/
PeayBASIC source code :
https://github.com/AZHenley/PeayBASIC
迷你操作系统
在课堂上,操作系统的数据结构和算法看起来太抽象而没啥用处。但实际上,他们是非常有用的。多年来,我把操作系统的基本概念应用到了广阔的领域,如游戏编程,甚至预测人类行为的模型。 实现一个操作系统能帮助我们深入地理解底层的情况。
由于依赖硬件,所以刚开始的时候,学习曲线陡峭,有不少障碍,但是如果跟随一本书或者教程,你可以快速地得到一个可以启动工作的OS,并且能运行你自己的程序。
我强烈推荐这本免费的书籍:《Making a RISC-V Operating System using Rust.》
需要学习的内容
交叉编译
操作系统自举
BIOS
中断
x86 modes
内存管理和分页
调度(e.g., round robin)
文件系统 (e.g., FAT)
进一步阅读:
OSDev.org's wiki of resources
https://wiki.osdev.org/Main_Page
Making a RISC-V Operating System using Rust
http://osblog.stephenmarz.com/index.html
《操作系统概念》
如果你能走到这一步,已经非常厉害了,但是....
如果你觉得还是不够难,试试这两个:
电子表格
电子表格(例如Excel),把文本编辑器和编译器这两大挑战结合起来了, 需要学会怎么表示单元格的内容,并且实现一个解释器,以便对单元格的内容进行公式计算。
进一步阅读:
有向无环图
https://en.wikipedia.org/wiki/Directed_acyclic_graph
反应式编程
https://en.wikipedia.org/wiki/Reactive_programming
《Spreadsheet Implementation Technology》
视频游戏控制台模拟器
为视频游戏写一个模拟器(或者虚拟机)把编译器和操作系统的挑战给结合起来了,当你把别人的游戏在你的模拟器上运行起来以后,那种成就感相当棒。
这个模拟器其实就是虚拟机,能让那些游戏以为自己在真实的CPU和其他硬件上运行,难度相当高。我建议从模拟CHIP-8开始,这是一个简单的虚拟控制台,然后再转移到一个真正的视频游戏控制台。
NES、SNES、Gameboy和Gameboy的高级版本都是可以模拟的,已经有了大量的文档和开源模拟器。尽管它们都有自己的怪癖,使事情变得有趣(例如,某些游戏可能依赖于特定硬件的无文档记录的bug /特性)。还有PICO-8,它已经成为一个非常有利可图的“幻想”游戏机。
进一步阅读:
Writing a Chip-8 emulator
https://aymanbagabas.com/2018/09/17/chip-8-emulator.html
JavaScript Chip-8 Emulator
http://blog.alexanderdickson.com/javascript-chip-8-emulator
《How to Emulate a Game Boy》
https://blog.ryanlevick.com/DMG-01/public/book/
PyBoy source code
https://github.com/Baekalfen/PyBoy
后记:我觉得这篇文章列举的项目都偏重基础,非常适合在校的大学生,可以锻炼最基本的编程能力,建议多做几个。如果已经工作了,很难会有大块的时间去折腾了,可以考虑选一个自己最感兴趣的去实现。
原文链接:
http://web.eecs.utk.edu/~azh/blog/challengingprojects.html
往期精彩回顾