GHOST's Blog

发表于 更新于 分类于

《算法（第4版）》笔记

归并

归并排序基于“归并”这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// c++
template<class T>
void merge(T& a, int lo, int mid, int hi, T& aux)
{
    // 将a[lo .. mid]和a[mid+1 .. hi]归并
    int i = lo;
    int j = mid + 1;

    for (int k=lo; k<=hi; ++k)
        aux[k] = a[k];

    for (int k=lo; k<=hi; ++k)
    {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (aux[j] < aux[i])
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}
阅读全文 »

发表于 更新于 分类于

《算法（第4版）》笔记

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

选择排序的缺点：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// c++
// 将容器a按升序排列
template<class T>
void selection_sort(T& a)
{
    int n = a.size();
    for (int i=0; i<n; ++i)
    {
        int min = i;
        for (int j=i+1; j<n; ++j)
        {
            if (a[j] < a[min])
                min = j;
        }

        std::swap(a[i], a[min]);
    }
}
阅读全文 »

发表于 更新于 分类于

《SDL Game Development》笔记

坐标系
原点：左上角

SDL扩展
SDL_image
支持多种格式图片加载：BMP GIF PNG TGA PCX …
SDL_net
跨平台网络库
SDL_mixer
audio mixer library. 支持MP3 MIDI OGG
SDL_ttf
支持TrueType字体
SDL_rtf
support the rendering of the Rich Text Format (RTF).

SDL_Init()
初始化标识

1
2
3
4
5
6
7
SDL_INIT_HAPTIC      Force feedback subsystem  力反馈
SDL_INIT_AUDIO       Audio subsystem
SDL_INIT_VIDEO       Video subsystem
SDL_INIT_TIMER       Timer subsystem
SDL_INIT_JOYSTICK    Joystick subsystem
SDL_INIT_EVERYTHING  All subsystems
SDL_INIT_noparachute Don't catch fatal signals

查看一个子系统是否已被初始化：

1
2
if (SDL_WasInit(SDL_INIT_VIDEO) != 0)
    cout << "video was initialized";
1
2
3
4
5
SDL_CreateRenderer()
SDL_RENDERER_SOFTWARE      Use software rendering
SDL_RENDERER_ACCELERATED   Use hardware acceleration
SDL_RENDERER_PRESENTVSYNC  Synchronize renderer update with screen's refresh rate
SDL_RENDERER_TARGETTEXTURE Supports render to texture

游戏程序结构
初始化
游戏循环：获取输入 物理运算 渲染
退出

window flags

1
2
3
4
5
6
7
8
9
10
11
12
SDL_WINDOW_FULLSCREEN      Make the window fullscreen
SDL_WINDOW_OPENGL          Window can be used with as an OpenGL context
SDL_WINDOW_SHOWN           The window is visible
SDL_WINDOW_HIDDEN          Hide the window
SDL_WINDOW_BORDERLESS      No border on the window
SDL_WINDOW_RESIZABLE       Enable resizing of the window
SDL_WINDOW_MINIMIZED       Minimize the window
SDL_WINDOW_MAXIMIZED       Maximize the window
SDL_WINDOW_INPUT_GRABBED   Window has grabbed input focus
SDL_WINDOW_INPUT_FOCUS     Window has input focus
SDL_WINDOW_MOUSE_FOCUS     Window has mouse focus
SDL_WINDOW_FOREIGN         The window was not created using SDL

程序基本结构

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
#include <SDL.h>

SDL_Window* g_pWindow = 0;
SDL_Renderer* g_pRenderer = 0;

int main(int argc, char* argv[])
{
	// initialize SDL
	if (SDL_Init(SDL_INIT_EVERYTHING) >= 0)
	{
		// if succeeded create our window
		g_pWindow = SDL_CreateWindow("Chapter 1: Setting up SDL",
			SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED,
			640, 480,
			SDL_WINDOW_SHOWN);

		// if the window creation succeeded create our renderer
		if (g_pWindow != 0)
		{
			g_pRenderer = SDL_CreateRenderer(g_pWindow, -1, 0);
		}
	}
	else
		return 1; // sdl could not initialize

	// everything succeeded lets draw the window
	bool bQuit = false;
	while (true)
	{
		SDL_Event event;
		if (SDL_PollEvent(&event))
		{
			switch (event.type)
			{
			case SDL_QUIT:
				bQuit = true;
				break;
			}
		}
		if (bQuit)
			break;

		// set to black
		// This function expects Red, Green, Blue and Alpha as color values
		SDL_SetRenderDrawColor(g_pRenderer, 0, 0, 0, 255);

		// clear the window to black
		SDL_RenderClear(g_pRenderer);

		// show the window
		SDL_RenderPresent(g_pRenderer);
	}

	// set a delay before quitting
	//SDL_Delay(5000);

	// clean up SDL
	SDL_Quit();

	return 0;
}

绘制图片过程

  1. 加载图片获得SDL_Surface
  2. 根据Surface获得SDL_Texture
  3. 获得纹理尺寸：SDL_QueryTexture
  4. 渲染：SDL_RenderCopy/SDL_RenderCopyEx 需要Renderer参数

SDL使用两种数据结构渲染到屏幕
SDL_Surface 像素集 使用软件渲染（not GPU）
SDL_Texture 使用硬件加速

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SDL_Texture* m_pTexture
SDL_Rect m_sourceRectangle;
SDL_Rect m_destinationRectangle;

// 根据图片创建SDL_Texture
SDL_Surface* pTempSurface = SDL_LoadBMP("asserts/rider.bmp");
m_pTexture = SDL_CreateTextureFromSurface(m_pRenderer, pTempSurface);
SDL_FreeSurface(pTempSurface);

// 获得图片的大小
SDL_QueryTexture(m_pTexture, NULL, NULL,
    &m_sourceRectangle.w, &m_sourceRectangle.h);

SDL_RenderClear();
SDL_RenderCopy(m_pRenderer, m_pTexture,
    &m_sourceRectangle, &m_destinationRectangle);
SDL_RenderPresent();

源矩形 目标矩形 参数传入0 将整个纹理渲染到整个窗口。

SDL_GetTicks() 毫秒

SDL_RenderCopyEx() 支持旋转和翻转Flip

SDL_image
sdl2_image.lib

1
2
#include <sdl_image.h>
SDL_Surface* pTempSurface = IMG_Load("animate.png");

Fixed frames per second (FPS) is
not necessarily always a good option, especially when your game includes more
advanced physics. It is worth bearing this in mind when you move on from this
book and start developing your own games. Fixed FPS will, however, be fine for
the small 2D games, which we will work towards in this book.

固定帧频

1
2
3
4
5
6
7
8
9
10
const int FPS = 60;
const int DELAY_TIME = 1000.0f / FPS;  // 1000毫秒
while (...)
{
    frameStart = SDL_GetTicks();  // 毫秒
    ...
    frameTime = SDL_GetTicks() - frameStart;
    if (frameTime < DELAY_TIME)
        SDL_Delay((int)(DELAY_TIME - frameTime));
}
1
2
3
4
5
6
7
8
9
10
11
12
SDL joystick event
SDL_JoyAxisEvent   Axis motion information
SDL_JoyButtonEvent Button press and release information
SDL_JoyBallEvent   Trackball event motion information
SDL_JoyHatEvent    Joystick hat position change

SDL joystick event    Type value
SDL_JoyAxisEvent      SDL_JOYAXISMOTION
SDL_JoyButtonEvent    SDL_JOYBUTTONDOWN or
                      SDL_JOYBUTTONUP
SDL_JoyBallEvent      SDL_JOYBALLMOTION
SDL_JoyHatEvent       SDL_JOYHATMOTION

不同的游戏控制器 按钮和轴可能有不同的值 比如Xbox360 controller, PS3 controller
Xbox360 controller:
Two analog sticks
Analog sticks press as buttons
Start and Select buttons
Four face buttons: A, B, X, and Y
Four triggers: two digital and two analog
A digital directional pad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (SDL_WasInit(SDL_INIT_JOYSTICK) == 0)
    SDL_InitSubSystem(SDL_INIT_JOYSTICK);
if (SDL_NumJoysticks() > 0)
{
    for (int i=0; i<SDL_NumJoysticks(); ++i)
    {
        SDL_Joystick* joy = SDL_JoystickOpen(i);
        if (SDL_JoystickOpened(i) == 1)
            m_joysticks.push_back(joy);
    }
    SDL_JoystickEventState(SDL_ENABLE);
}

SDL_JoystickClose(joy);

分辨是哪个控制器的事件

1
2
if (event.type == SDL_JOYAXISMOTION)
    int whichOne = event.jaxis.which;

控制器按钮
SDL_JoystickNumButtons
event.jbutton.button // 按钮ID

鼠标事件

1
2
3
4
5
6
7
8
9
SDL Mouse Event        Purpose
SDL_MouseButtonEvent   A button on the mouse has been pressed or released
SDL_MouseMotionEvent   The mouse has been moved
SDL_MouseWheelEvent    The mouse wheel has moved

SDL Mouse Event        Type Value
SDL_MouseButtonEvent   SDL_MOUSEBUTTONDOWN or SDL_MOUSEBUTTONUP
SDL_MouseMotionEvent   SDL_MOUSEMOTION
SDL_MouseWheelEvent    SDL_MOUSEWHEEL
1
2
3
4
5
// 鼠标按钮
// SDL numbers these as 0 for left, 1 for middle, and 2 for right.

if (event.type == SDL_MOUSEBUTTONDOWN)
    if (event.button.button == SDL_BUTTON_LEFT)

event.type SDL_MOUSEMOTION
event.motion.x
event.motion.y

// 键盘
1 表示按下 0 表示没有按下
SDL_GetKeyboardState(int* numkeys)
Uint8* m_keystates;
m_keystates = SDL_GetKeyboardState(0);
SDL_Scancode key;
if (m_keysttes[key] == 1)

有限状态机
需要能够处理以下情况：
Removing one state and adding another
Adding one state without removing the previous state
Removing one state without adding another

Game
GameObject
TextureManager // 负责加载图片文件，负责绘制，纹理ID
InputHandler
GameState
GameStateMachine
GameObjectFactory
StateParser

Distributed Factory
class GameObjectFactory
std::map<std::string, BaseCreator*> m_creators;
registerType(std::string typeID, BaseCreator* pCreator);

https://github.com/ReneNyffenegger/development_misc/tree/master/base64.
The base64.h and base64.cpp files can be added directly to the project.

1
2
3
4
5
6
7
8
9
10
11
12
SDL_Mixer
Mix_OpenAudio(int frequency, Uint16 format, int channels, int chunksize)
Mix_OpenAudio(22050, AUDIO_S16, 2, 4096);
std::map<std::string, Mix_Chunk*> mSfxs;
std::map<std::string, Mix_Chunk*> mMusic;

Mix_Music* music = Mix_LoadMUS(filename);  // ogg
Mix_Chunk* chunk = Mix_LoadWAV(filename);  // wav

Mix_PlayMusic()     // Mix_Music
Mix_PlayChannel()   // Mix_Chunk
Mix_CloseAudio();

SDL_SetTextureAlphaMod()

发表于 更新于 分类于

开发环境配置

http://tjumyk.github.io/sdl-tutorial-cn/contents.html

VS 新建项目选择控制台程序，链接属性中选择子系统“/SUBSYSTEM:WINDOWS”。

在屏幕上显示一张图片

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
#include <SDL/SDL.h>

int main(int argc, char *args[])
{
  SDL_Surface *hello = nullptr;
  SDL_Surface *screen = nullptr;

  SDL_Init(SDL_INIT_EVERYTHING);

  // 设置窗口
  screen = SDL_SetVideoMode(640, 480, 32, SDL_SWSURFACE);

  // 加载图像
  hello = SDL_LoadBMP("hello.bmp");

  // 将图像应用到窗口上
  SDL_BlitSurface(hello, nullptr, screen, nullptr);

  // 更新窗口
  SDL_Flip(screen);

  SDL_Delay(2000);

  // 释放资源
  SDL_FreeSurface(hello);
  SDL_Quit();
  return 0;
}
阅读全文 »

发表于 更新于 分类于

以下摘自《敏捷软件开发：原则、模式与实践》。

可持续的开发速度：

软件项目不是全速短跑，它是马拉松长跑。那些一跃过起跑线就开始尽力狂奔的团队将会在远离终点前就筋疲力尽。为了快速地完成开发，团队必须要以一种可持续的速度前进。团队必须保持旺盛的精力和敏锐的警觉。团队必须要有意识地保持稳定、适中的速度。

XP（极限编程）的规则不允许团队加班工作。在版本发布前的一个星期是该规则的唯一例外。如果发布目标就在眼前并且能够一蹴而就，则允许加班。

发表于 更新于 分类于

以下摘自《人月神话》，讨论了开发团队的组建以及运作。

在计算机领域的会议中，常常听到年轻的软件经理声称，他们喜欢由一流人才组成的小型、精干的队伍，而不是那些几百人的大型团队，这里的“人”当然暗指平庸的程序员。其实我们也经常有相同的看法。

软件经理很早就认识到优秀程序员和较差程序员之间生产率的差异。

我常常重复这样一个观点，需要协作沟通的人员数量影响着开发成本，因为成本的主要组成部分是相互的沟通和交流，以及更正沟通不当引起的不良结果（系统调试）。这一点，也暗示系统应该由尽可能少的人员来开发。

如果在一个200人的项目中，有25个最能干和最有开发经验的项目经理，那么开除剩下的175名程序员，让项目经理来编程开发。

阅读全文 »

发表于 更新于 分类于

摘自前言

从前，有位咨询顾问造访客户调研其开发项目。系统核心是个类继承体系，顾问看了开发人员所写的一些代码。他发现整个体系相当凌乱，上层超类对于系统的运作做了一些假设，下层子类实现这些假设。但是这些假设并不适合所有子类，导致覆写（override）工作非常繁重。只要在超类做点修改，就可以减少许多覆写工作。在另一些地方，超类的某些意图并未被良好理解，因此其中某些行为在子类内重复出现。还有一些地方，好几个子类做相同的事情，其实可以把它们搬到继承体系的上层去做。

这位顾问于是建议项目经理看看这些代码，把它们整理一下，但是经理并不热衷于此，毕竟程序看上去还可以运行，而且项目面临很大的进度压力。于是经理说，晚些时候再抽时间做这些整理工作。

顾问也把他的想法告诉了在这个继承体系上工作的程序员，告诉他们可能发生的事情。程序员都很敏锐，马上就看出问题的严重性。他们知道这并不全是他们的错，有时候的确需要借助外力才能发现问题。程序员立刻用了一两天的时间整理好这个继承体系，并删掉了其中一半代码，功能毫发无损。他们对此十分满意，而且发现在继承体系中加入新的类或使用系统中的其他类都更快、更容易了。

项目经理并不高兴。进度排得很紧，有许多工作要做。系统必须在几个月之后发布，而这些程序员却白白耗费了两天时间，干的工作与要交付的多数功能毫无关系。原先的代码运行起来还算正常，他们的新设计看来有点过于追求完美。项目要交付给客户的，是可以有效运行的代码，不是用以取悦学究的完美东西。顾问接下来又建议应该在系统的其他核心部分进行这样的整理工作，这会使整个项目停顿一至二个星期。所有这些工作只是为了让代码看起来更漂亮，并不能给系统添加任何新功能。

阅读全文 »

发表于 更新于 分类于

第一本Docker书

简介

Docker是一个能够把开发的应用程序自动部署到容器的开源引擎。

Docker容器拥有很高的性能，同时同一台宿主机中也可以运行更多的容器，使用户可以尽可能充分地利用系统资源。

Docker设计的目的就是要加强开发人员写代码的开发环境与应用程序要部署的生产环境的一致性，从而降低那种“开发时一切都正常，肯定是运维的问题”的风险。

Docker的目标之一就是缩短代码从开发、测试到部署、上线运行的周期，让你的应用程序具备可移植性，易于构建，并易于协作。

容器是镜像的实例。容器是基于镜像启动起来的。镜像是Docker生命周期中的构建或打包阶段，而容器则是启动或执行阶段。

阅读全文 »

发表于 更新于 分类于

前几天为电脑新加了块硬盘，并且将Fedora安装到了新硬盘上。以下是安装使用过程中遇到的问题，在此记录一下。

新加硬盘后Windows无法启动

网上搜了之后，据说是数据线的问题，于是换了根数据线，谢天谢地，好像是很久以前组装电脑买的主板带了两根数据线。换了另一根数据线后成功开机了，1T的硬盘分了500G给Windows，剩下的留给Linux。

安装Fedora时提示自动分区失败

原因是从光盘启动时，启动项选择的是UEFI模式，不使用UEFI模式则自动分区成功，安装一切顺利。安装光盘是使用Fedora官网下载的Fedora-24-Xfce-Live镜像刻录的。

阅读全文 »
0%