（机翻）每个程序员都应该尝试的具有挑战性的项目

from：Challenging projects every programmer should try     作者：Austin Z. Henley       翻译：沉浸式翻译v0.7.9 文章续集一：每个程序员都应该尝试更具挑战性的项目 续集二：每个程序员都应该尝试的具有挑战性的算法和数据结构   2019 年 12 月 14 日更新：这篇文章引发了 Hacker News 和 Reddit 上的大量讨论。我收集了一些建议的项目，并将它们放在本文末尾的列表中。

我与很多学生和专业开发人员交谈过，他们经常想要启动一个业余项目，但不确定要构建什么。下面是一些教会了我很多东西的软件项目。事实上，它们很棒，因为您可以多次构建它们并每次都能学到新东西。因此，每当我不知道要构建什么或者我想学习一种新的编程语言或框架时，我都会从以下之一开始：

• Text editor 文本编辑器
• 2D game - Space Invaders
  2D 游戏 - 太空侵略者
• Compiler - Tiny BASIC
  编译器 - Tiny BASIC
• Mini operating system 迷你操作系统
• Spreadsheet (hard!) 电子表格（很难！）
• Video game console emulator (hard!)
  视频游戏控制台模拟器（很难！）

Text Editor 文本编辑器

我们每天都会使用文本编辑器，但是你知道它到底是如何工作的吗？忽略您最喜欢的编辑器具有的所有奇特功能，您将如何实现支持可移动文本光标以及选择、插入和删除文本的文本框？不，您不能使用您最喜欢的 GUI 框架中的内置文本框组件！

最大的挑战是弄清楚如何将文本文档存储在内存中。我的第一个想法是使用数组，但如果用户在文档末尾以外的任何地方插入文本，那么它的性能会很糟糕。幸运的是，有一些很好的数据结构可以学习来解决这个问题。

另一个障碍是了解文本光标在流行编辑器中的行为方式。例如，如果我在光标位于文档中间的情况下按向上箭头键，光标会移动到哪里？同一个专栏？如果该线较短则不会。继续往上按。一旦一行足够长，光标将快速返回到原始列。事实证明，光标有该列的记忆，并试图返回该列。正是这些细节我在尝试实现之前从未注意到。

实现基本编辑器后，我挑战您再实现两个功能：撤消/重做和自动换行。以有效的方式实现撤消/重做让我大吃一惊！我首先尝试保留一系列先前的状态，然后尝试“备忘录”模式，最后选择“命令”模式。自动换行迫使您将文本行的视觉方面与记忆方面分开。

Things to learn: 学习内容：

• Data structures for storing the text: array, rope, gap buffer, piece table.
  用于存储文本的数据结构：数组、绳索、间隙缓冲区、片段表。
• Behavior and implementation of the text cursor.
  文本光标的行为和实现。
• Design patterns for undo/redo: memento, command.
  撤消/重做的设计模式：备忘录、命令。
• Abstractions to separate the visual and memory aspects of the text.
  用于分离文本的视觉和记忆方面的抽象。

Further reading: 进一步阅读：

• Text Editor: Data Structures (web)
  文本编辑器：数据结构（网络）
• Design and Implementation of a Win32 Text Editor (web)
  Win32文本编辑器的设计与实现(web)
• Data Structures and Algorithms in Java (Amazon)
  Java 中的数据结构和算法（亚马逊）

2D game - Space Invaders
2D 游戏 - 太空侵略者

即使是最简单的游戏也需要一些独特的数据结构和设计模式。这里的想法是从头到尾实现一个定义明确的游戏，而不会陷入其他有趣的东西（例如游戏设计和艺术）。另外，最好使用准系统 2D 图形库（例如 SDL、SFML、PyGame），而不是会隐藏所有有趣部分的大型游戏引擎。

首先，您必须学习在屏幕上绘图。我不知道这是如何运作的。实际上，您正在清除屏幕，然后快速连续地绘制屏幕的每个部分，每秒多次，以创建对象正在移动的效果。

其次，您将了解有关游戏循环的所有内容。游戏在绘图、获取用户输入和处理游戏逻辑之间有效地循环。

第三，您将学习如何处理用户输入。我从来没有注意到最初按下、按住和释放按键或鼠标按钮的微妙之处，更不用说处理双击之类的事情了。您多久检查一次用户输入？如果你不断地检查，那就意味着游戏的其余部分被冻结了！

第四，您将学习如何创建和管理所有游戏对象及其状态。例如，如何生成动态数量的敌人？工厂模式有很大帮助。

第五，您将学习如何应用游戏的逻辑。子弹位置什么时候更新？何时会有更多敌人出现在屏幕上？你怎么知道敌人何时被消灭？比赛什么时候结束？在制作游戏之前我从未使用过模运算符，但它散布在我的游戏代码中。

一旦你让基本的游戏运行起来，添加一个标题屏幕菜单、一个游戏结束屏幕，确保游戏即使在不同的计算机上也以相同的速度运行，并探索如何使用人工智能实现更有趣的敌人。还不够吗？添加着色器效果、声音和在线多人游戏！

Things to learn: 学习内容：

• Drawing to the screen.
  绘制到屏幕上。
• Handling user input. 处理用户输入。
• Game loop. 游戏循环。
• Creating and managing a dynamic number of objects (e.g., factory pattern).
  创建和管理动态数量的对象（例如工厂模式）。
• State machines for enemy AI.
  敌方人工智能的状态机。
• Playing sound. 播放声音。
• Using shaders. 使用着色器。
• Networking for online features.
  网络在线功能。

Further reading: 进一步阅读：

• Game Programming Patterns (Amazon, web)
  游戏编程模式（亚马逊、网络）
• Data Structures for Game Programmers (Amazon)
  游戏程序员的数据结构（亚马逊）
• Programming Game AI by Example (Amazon)
  通过示例进行游戏 AI 编程（亚马逊）
• The 8 lessons I learned from releasing 8 video games (web)
  我从发布 8 个视频游戏中学到的 8 个教训（网页版）

Compiler - Tiny BASIC
编译器 - Tiny BASIC

我参与过的最令人大开眼界的项目是编译器。即使是现在，如果我周日下午有空来做一些编码，很可能它是一个编译器。当你创造出一些东西并让其他人能够创造出更多东西时，这种感觉真是太棒了。通过实现一个，我必须了解更多关于编译器的复杂性，这是我通常永远不会想到的（例如，表达式何时进行隐式类型转换）。

我建议从头开始为一种非常小的类似 BASIC 的语言（请参阅 Tiny BASIC）编写编译器，然后编译为您熟悉的任何其他语言。例如，您可以用 Python 编写一个输出 C# 代码的 Tiny BASIC 编译器。它不必输出汇编或C！避免这些将使您专注于编译器本身。

第一个障碍是弄清楚如何对输入代码进行词法分析（或标记化）。然后您将解析代码，即检查输入的结构并生成代码的树表示。递归下降解析技术很漂亮！接下来，您将从语义上检查输入，确保代码有意义并且遵循类型规则。最后，您可以生成输出！

该项目有大量现有资源可以帮助您，并且一个简单的编译器可以在几天内完成。不要让行话吓到你。另外，您可以添加的内容是无限的！一旦基本编译器开始工作，您就可以添加标准库（在 PeayBASIC 中我添加了简单的 2D 图形功能）、优化过程并改进错误消息。最后，你应该用你自己的语言编写一些示例程序来向世界炫耀！

Things to learn: 学习内容：

• Lexical analysis 词法分析
• Syntactic analysis 句法分析
• Recursive descent parsing
  递归下降解析
• Abstract syntax tree 抽象语法树
• Semantic analysis 语义分析
• Optimization passes 优化通过
• Code generation 代码生成

Further reading: 进一步阅读：

• My tutorial: Let's make a Teeny Tiny compiler (web)
  我的教程：让我们制作一个 Teeny Tiny 编译器（网络）
• Crafting Interpreters (Amazon, web)
• Write an Interpreter in Go (Amazon)
  用 Go 编写解释器（亚马逊）
• Let's Build a Compiler (web)
  让我们构建一个编译器（网络）
• PeayBASIC source code (GitHub)
  PeayBASIC 源代码 (GitHub)

Mini Operating System 迷你操作系统

多年来，我发现自己将操作系统的基本概念应用到了各种领域，例如游戏，甚至人类行为的预测模型。在课堂环境中，操作系统使用的算法和数据结构可能看起来抽象或无用，但它们确实很有用。实施操作系统还帮助我更多地了解幕后发生的事情。

由于它依赖于硬件，因此有一些学习曲线和一些入门障碍。但是，通过阅读书籍或教程，您应该能够获得一个可以运行您自己的程序的可启动操作系统。我强烈推荐我同事的免费在线书籍《使用 Rust 制作 RISC-V 操作系统》。

Things to learn: 学习内容：

• Cross compiling 交叉编译
• Bootloading 引导加载
• BIOS interrupts BIOS 中断
• x86 modes x86 模式
• Memory management and paging
  内存管理和分页
• Scheduling (e.g., round robin)
  调度（例如，循环）
• File systems (e.g., FAT)
  文件系统（例如 FAT）

Further reading: 进一步阅读：

• OSDev.org's wiki of resources (web)
  OSDev.org 的 wiki 资源（网络）
• Making a RISC-V Operating System using Rust (web)
  使用 Rust 制作 RISC-V 操作系统 (web)
• Operating System Concepts (Amazon)
  操作系统概念（亚马逊）

对你来说还不够困难吗？尝试这两个项目：

Spreadsheet 电子表格

电子表格应用程序（例如 Excel）将文本编辑器的一些挑战与编译器的挑战结合在一起。您必须学习如何表示内存中的单元格内容并实现用于方程的编程语言的解释器。

Further reading: 进一步阅读：

• Directed acyclic graph (web)
  有向无环图（网络）
• Reactive programming paradigm (web)
  响应式编程范式（网络）
• Spreadsheet Implementation Technology (Amazon)
  电子表格实施技术（亚马逊）

Video game console emulator
视频游戏控制台模拟器

为视频游戏控制台编写模拟器（或虚拟机）将编写编译器、操作系统和游戏引擎的挑战结合在一起。用自己的模拟器玩一下别人制作的真实游戏，真是太有成就感了！

模拟真实的视频游戏控制台意味着编写一个虚拟机，假装其功能与实际的 CPU 和其他硬件组件一样。这允许您使用模拟器运行专为视频游戏控制台设计的游戏。

我建议首先模拟 CHIP-8，这是一个简单的虚构控制台，然后再转向真正的视频游戏控制台。 NES、SNES、Gameboy 和 Gameboy Advance 都非常易于模拟，已经有大量文档和开源模拟器，尽管它们都有自己的怪癖以使事情变得有趣（例如，某些游戏可能依赖于未记录的错误） /特定硬件的功能）。还有PICO-8，它已经成为一款非常赚钱的“幻想”游戏机。

Further reading: 进一步阅读：

• Writing a Chip-8 emulator (web)
  编写 Chip-8 模拟器（网络）
• JavaScript Chip-8 Emulator (Wayback Machine)
  JavaScript Chip-8 模拟器（时光机）
• How to Emulate a Game Boy in Rust (Wayback Machine)
  如何在 Rust 中模拟 Game Boy（时光机）
• PyBoy source code (GitHub)
  PyBoy 源代码 (GitHub)

如果您有任何其他项目想法，请告诉我！以下是来自 Hacker News、Reddit、Twitter 和我收到的电子邮件的建议列表：

• Database from scratch 数据库从头开始
• Ray tracer 射线追踪器
• MS Paint clone
• Vector graphics editor 矢量图形编辑器
• Image decoder 图像解码器
• Chatroom web app 聊天室网络应用程序
• Digits of pi calculator
  圆周率计算器的位数
• Common terminal utilities (e.g., grep)
  常见的终端实用程序（例如 grep）
• FTP client and server
  FTP 客户端和服务器