26 марта 2015 в 10:13

Как я спас несколько жизней оптимизацией и немного о работе в Zeptolab

Привет!

23derevo перед выступлением на Mobius попросил меня рассказать немного о процессе клиентской разработки в Zeptolab.



Начну с того, что мы пишем на C++ и на своём фреймворке, от любого клиентского устройства нам нужен только контекст OpenGL. Дальше мы с нуля строим свой интерфейс, свои контролы и так далее. Соответственно, чтобы взять девелопера в команду, в теории, ему достаточно знать плюсы. На практике это немного не так.



О работе


Я пришёл в Zeptolab ещё когда у нас было целых три разработчика: CTO, iOS-девелопер и Android-девелопер. До этого я учился в ШАД Яндекса и параллельно по работе пилил базу таможенной документации с возможностью Rich-форматирования, хранения файлов и изображений – в общем, своего рода MSDN, только для таможенных нужд. До сих пор она используется, и до сих пор ей только начинают находиться аналоги.

Суперкрутых технологических знаний у меня не было, я занимался графикой, писал небольшие проекты на OpenGL, делал шейдеры. Этого, в целом, хватило, чтобы начать уже учиться по ветке мобильной разработки.

На мой взгляд, самое важное для кандидата (и разработчика вообще) – это общая сообразительность, технический кругозор и техническое мышление. Кстати, на собеседовании мне задавали пресловутую задачу про круглые люки. Сейчас я сам провожу собеседования, и даю похожие абстрактные задачи. Оскомину они набивают некоторым кандидатам из-за того, что список таких задач меняется редко (если давать рандом, то не будет общей метрики – будет не очень честно по отношению к кандидатам). Но, учитывая, что они «утекают» за пределы собеседований, мы обычно готовим ещё пару своих задач, чтобы проверить, не читерит ли кандидат. Если с логикой всё в порядке, то незнание каких-то синтаксических особенностей языка — проблема меньшего масштаба. Синтаксис можно выучить, паттерны программирования тоже изучаются, а вот соображать, увы, нужно сразу.

Вообще, кодер тем и отличается от разработчика, что последний умеет придумывать идеи решения задач. В одной известной крупной компании работает мой хороший друг. У них российский офис занят только тем, что придумывает алгоритмы, проверяет их на Питоне или C# для прототипов, а потом отдаёт результаты подразделениям в Индии и Китае. Там уже далёкие кодеры без фантазии, но с предельным педантизмом и с чисто азиатским упорством берут описанные идеи и идеально реализуют их в коде для микроконтроллеров на C++ или C под каждое устройство.

Я бы советовал тем, кто ищет работу сразу после университета, получить рейтинг в районе 2000 на Codeforces. Если вы там будете слегка жёлтым, это – высокие шансы пройти, например, в Гугл. Кроме того, вы достаточно быстро поймёте, что на первом месте — способность думать и решать уникальные задачи, когда конкретные технологии уже изучаются «по месту» до необходимого (или достаточного) уровня.

Пара слов о художниках


Сначала у нас был Сocos2D. Хороший фреймворк, но многие вещи нас просто не устраивали по реализации, поэтому мы начали писать свою систему. Достаточно быстро удалось реализовать на C++ очень крутую систему анимаций и хорошую подготовку ресурсов. Про анимацию мы уже рассказывали, если коротко – она готовится во Flash, потом мы парсим FLA-файлы, а потом воссоздаём те же анимации в приложении. Самым главным для нас всегда был упор на качество. В случае анимаций – это плавность: художники часто стоят за спиной у программистов и говорят, что не так. Без тренировки нельзя увидеть, где и что незначительно дёргается, но художники это точно чувствуют. Обычный человек не сможет понять, что не так, да и не всегда сможет это описать, даже если увидит. Но почувствует, часто не очень сознательно, что «шероховато». Наши художники добиваются идеальной для себя картинки, и умеют объяснять техническим языком, что надо изменить.



На конференции наши ребята расскажут, как конкретно мы добивались такого качества картинки и покажут, что под капотом фреймворка. Я расскажу про эволюцию наших технологий, про подготовку ресурсов. Очень важно контролами попадать ровно пиксель в пиксель, правильно готовить шрифты, учитывать low-res девайсы и многое другое. Опять же, конкретные примеры я покажу на конференции.



Для меня, пожалуй, наибольший кайф – это встать за спиной художника и смотреть, как он создает шедевр из ничего. Иногда они так же смотрят на нас и пытаются понять, что мы делаем. Нам в разработке кажется, что хороших художников на рынке мало, и найти таких крутых нереально сложно. Им кажется, что разработчиков, понимающих, что им нужно, нереально мало.



Кстати, при всём их искренне гуманитарном образовании, проблем с технической частью замечено ни разу не было. Задачи формулируют отлично, общую архитектуру представляют. Был даже такой забавный случай: сфотографировали для контеста на Codeforces мы художника в роли разработчика, для прикола. Очки, сложное лицо, мысль. Так вот, он после этого внезапно стал писать код на JavaScript. Сначала были совсем простые макросы для Фотошопа и для Флеша. Потом он за несколько месяцев, фактически, прошёл всю историю эволюции разработки, открывая для себя новые и новые возможности. Помню, в какой-то момент он подошёл и начал достаточно коряво объяснять концепцию, которая бы очень помогла ему писать сложные скрипты: через некоторое время я понял, что он хочет ставить breakpoint'ы и смотреть значения переменных. Сам дошёл до использования assert'ов. До этого над его кодом мы иногда украдкой смеялись: выражения он мешал в одну строчку, без отступов, выглядело действительно немного дико. А потом как-то незаметно стал делать очень крутые скрипты. Сейчас думаем, кого ещё сфотографировать со сложным лицом.
Но вернусь к фреймворку. У нас довольно много рутины, в частности, связанной с его постоянными доработками. Фреймворк развивается, появляется новое железо, новые требования, хочется своевременно разбираться с легаси-кодом. Из последних крупных задач, например, нам нужна была своя система частиц. Посмотрели, что есть в Unity, художники говорят — мегакруто, но нужно ещё вот это, вот это и вот так.

В результате задача свелась не только к написанию генератора частиц, но и к реализации удобного интерфейса. У нас есть несколько слоёв эмиссии, и частицы двигаются по разным законам. Произвольная формула для каждой очень сильно нагружала бы клиентские устройства (пришлось бы, фактически, парсить каждую отдельно), а общая была недостаточно гибкой для реализации задумок художников. Решили математикой – вывели некоторую общую формулу для каждой частицы, где изменением коэффициентов можно запускать хоть параболу, хоть синусоиду. И не тормозит, и есть визуальное богатство.

В команде



Раз в две недели мы учим сами себя. Парни (а сейчас у нас в команде 21 разработчик) изучают что-то новое, чем ещё не пользовались на других проектах, или же чего нет в других компаниях. Собирают всех, рассказывают, что нашли интересного. Это могут самые разные темы: начиная от того, как сделать загрузку субъективно быстрой для пользователя и заканчивая быстрым блюром фона за попапом (как сделано в King of Thieves). К нам регулярно приезжал в офис Михаил Мирзаянов (он, кстати, тренировал нашу сборную, занявшую первое место на ACM/ICPC). Прочитал 3 блока крутейших лекций по алгоритмам и структурам данных, показывал редкие малоизвестные структуры и задачи (например, про дерево отрезков, которое он же и независимо открыл одним из первых в мире и первый в России). Как обучение, мы ходили на трёхдневный тренинг Скотта Майерса (это который написал книгу «Effective Modern C++»).



Из примеров задач — в 2013 была опубликована достаточно большая статья по решениям широко известной NP-трудной задачи по упаковке текстурных атласов. По результатам одного из конкурсов на Codeforces к нам пришёл сильный алгоритмист. Прочитал статью, долго думал, потом написал свой алгоритм, улучшенную версию общеизвестного, который мы сразу же проверили на одном из наиболее сложно упаковываемых атласов. Если брать за 100% идеальную упаковку, то наш предыдущий алгоритм давал результат больше 120%, а новый на этом же наборе данных стал показывать 104%. На практике это означает снижение потребление памяти на мегабайты.

Вообще, на 500 миллионов инсталлов такие вещи выглядят очень забавно. Например, наша самая первая система хранения и загрузки изображений оперировала PNG-файлами, и на загрузку уровня на тестовом устройстве уходило около 15 секунд. Отпрофилировали, разобрались – большую часть времени занимало декодирование PNG. Я переписал этот код (потребовался новый свой внутренний формат хранения графики) — и на том же тестовом устройстве загрузка стала занимать 6 секунд. Сэкономлено 9 секунд, — мы раскатали новую систему хранения на все свои игры. Если считать 20 загрузок игры за некоторый базовый показатель, мне кажется, спасено этим минимум полсотни жизней. Дальше этот механизм ускорили еще на 20-30% по совету новичка, который то же самое делал на старом месте работы, потому что в какой-то момент несложные вычисления на процессоре перестали быть узким местом системы загрузки, все стало упираться в скорость чтения из хранилища. Доработали свой формат.
По оптимизации вообще достаточно много работы. Наши игры работают даже на старом железе, фреймворк поддерживает iOS 4.3 (сейчас iOS 5: изначально из-за партнёрского кода, потом мы стали использовать libc++, которая тоже доступня начиная с iOS 5, во второй версии фреймворка). Разработку совсем новых приложений и эксперименты мы делаем под топовые модели, потому что к концу разработки они как раз станут самым массовым устройством — но «старичков» не забываем. С тем же «Cut the Rope» большая часть выпуска – это контентные апдейты. Старый код не портим. Новые игры уже куда богаче визуально, но и требования к железу у них выше.

Прототипирование у нас делается очень быстро, быстрее, чем во многих студиях. Геймдизайнер выдаёт концепт, затем за 1-2 дня кто-нибудь из разработчиков делает «работу мечты» — собирает с нуля прототип без графики, на примитивах. Если прыжки шарика и квадрата после этого штырят геймдизайнера – идёт в работу дальше. Естественно, прототипов куда меньше, чем обычных задач, но мы стараемся, чтобы каждый в команде рано или поздно написал свой.

Опять же, естественно, сразу это делаем на готовом проекте-заготовке, где есть все базовые вещи. Для людей, приходящих из разработки нативных мобильных приложений, это просто другой мир – стандартных контроллеров нет, подготовка ресурсов своя, вообще всё своё и даже не особо привязано к платформе. Те, кто работал с Unity — им интереснее копаться «под капотом», видя реализацию некоторых вещей, которые там сделать сложно. С Кокосом, в целом, на высоком уровне параллели есть, но всё равно интересно разобрать игру и посмотреть, как она работает внутри.

Немного про тестовые



Напоследок — мой небольшой спор с друзьями. Ниже под спойлером 5 образцов кода из тестовых заданий от разных людей. Код публикуется с согласия всех кандидатов. (осторожно, исходники довольно большие)

App.cpp
//
//  App.cpp
//  Asteroids
//
//  Created by xxxx
//
//

#include <string>

#include "App.h"
#include "RenderCommandPolygonConvex.h"
#include "Vec2.h"
#include "Color.h"
#include "GameMap.h"
#include "Camera.h"
#include "MapDrawObjectPolygon.h"
#include "MapObjectMovable.h"
#include "IMovable.h"
#include "MovableObjectTouch.h"
#include "MapObjectEmitter.h"
#include "EmitterLineContinuous.h"
#include "MovableInDirection.h"
#include "MapObjectHero.h"
#include "MapObjectAsteroid.h"
#include "MapObjectDebris.h"

const float LOGIC_MAP_WIDTH = 100;
const float GAMEPLAY_ACCELERATION = 0.003;

namespace
{
    void initAsteroidsEmitters(GameMapPtr gameMap, float logicMapWidth, std::vector<EmitterLineContinuousPtr>& asteroidEmitters)
    {
        
        for_each(asteroidEmitters.begin(), asteroidEmitters.end(), [](EmitterLineContinuousPtr emitter){emitter->die();});
            
        MapObjectEmitterPtr emitterMapObject(new MapObjectEmitter());
        EmitterLineContinuousPtr emitter(new EmitterLineContinuous(Vec2(-logicMapWidth*0.5f, 0), Vec2(logicMapWidth*1.5f, 0), Vec2(0, 0), 8, 25, -1, gameMap));
        emitter->setParticlesMapObject(MapObjectAsteroidPtr(new MapObjectAsteroid()));
        asteroidEmitters.push_back(emitter);
        emitterMapObject->setEmitter(emitter);
        gameMap->addMapObject(emitterMapObject, Vec2(0, -10), 0);
        
        MapObjectEmitterPtr emitterMapObject2(new MapObjectEmitter());
        EmitterLineContinuousPtr emitter2(new EmitterLineContinuous(Vec2(0, 0), Vec2(logicMapWidth, 0), Vec2(0, 1), 1, 30, -1, gameMap));
        emitter2->setParticlesMapObject(MapObjectAsteroidPtr(new MapObjectAsteroid()));
        emitterMapObject2->setEmitter(emitter2);
        asteroidEmitters.push_back(emitter2);
        gameMap->addMapObject(emitterMapObject2, Vec2(0, -10), 0);

        MapObjectEmitterPtr emitterMapObject3(new MapObjectEmitter());
        EmitterLineContinuousPtr emitter3(new EmitterLineContinuous(Vec2(0, 0), Vec2(logicMapWidth, 0), Vec2(0, 1), 3, 20, -1, gameMap));
        emitter3->setParticlesMapObject(MapObjectDebrisPtr(new MapObjectDebris()));
        emitterMapObject3->setEmitter(emitter3);
        asteroidEmitters.push_back(emitter3);
        gameMap->addMapObject(emitterMapObject3, Vec2(0, -10), 0);
        
        MapObjectEmitterPtr emitterMapObject4(new MapObjectEmitter());
        EmitterLineContinuousPtr emitter4(new EmitterLineContinuous(Vec2(0, 0), Vec2(logicMapWidth, 0), Vec2(0, 1), 1, 40, -1, gameMap));
        emitter4->setParticlesMapObject(MapObjectAsteroidPtr(new MapObjectAsteroid()));
        emitterMapObject4->setEmitter(emitter4);
        asteroidEmitters.push_back(emitter4);
        gameMap->addMapObject(emitterMapObject4, Vec2(0, -10), 0);
    }
}

App::App()
:time_(0)
{

}

void App::updateAndRender(float dtSec, std::vector<RenderCommandBasePtr>& renderCommands)
{
    update(dtSec);
    collectRenderData(renderCommands);
}

bool App::touch(const std::vector<TouchEvent>& events) const
{
    if (events.empty())
        return false;
    
    if (gameMap_)
        gameMap_->touch(events);
    
    return true;
}

void App::update(float dtSec)
{
    if (gameMap_)
        gameMap_->update(dtSec);
    
    tryRespawnHero();
    
    updateGameplayAcceleration();
    
    time_+= dtSec;
}

void App::resetGameplay()
{
    time_ = 0;
    ::initAsteroidsEmitters(gameMap_, LOGIC_MAP_WIDTH, asteroidEmitters_);
}

void App::tryRespawnHero()
{
    if (!hero_ || hero_->isReadyToDestruct() )
    {
        if (!gameMap_->hasObjectOfType(MAP_OBJECT_HERO_DEBRIS))
        {
            resetGameplay();
            
            hero_ = MapObjectHeroPtr(new MapObjectHero(Rect(0, 0, logicMapSize_.x, logicMapSize_.y)));
            gameMap_->addMapObject(hero_, Vec2(50, logicMapSize_.y - 10), 0);
        }
    }
}

void App::setScreenSize(int screenW, int screenH)
{
    screenSize_ = Vec2(screenW, screenH);
   
    float logicCellSize = screenW/LOGIC_MAP_WIDTH;
    
    logicMapSize_ = Vec2(screenW/logicCellSize, screenH/logicCellSize);
    CameraPtr camera = CameraPtr(new Camera(logicCellSize, logicCellSize));
    
    gameMap_ = GameMapPtr(new GameMap(Size(logicMapSize_.x, logicMapSize_.y), camera));
    gameMap_->setLiveAreaRect(Rect(-logicMapSize_.x/2, -10, logicMapSize_.x*2, logicMapSize_.y + 20));
    
    resetGameplay();
}


void App::collectRenderData(std::vector<RenderCommandBasePtr>& renderCommands) const
{
    gameMap_->collectRenderData(renderCommands);
}

void App::updateGameplayAcceleration()
{
    for (auto emitter: asteroidEmitters_)
    {
        emitter->setSpeedParticles(emitter->getSpeedParticles() + time_*GAMEPLAY_ACCELERATION);
    }
}


game.cpp
/*управление w,a,d для полета коробляб r для возобновления иры, space для выстрела*/



#include "stdafx.h"
#include <math.h>
#include <vector>
#include <iostream>
#include <fstream>
#include <glut.h> 
using namespace std;


const float Pi=3.14159265358;
float winwid=400;
float winhei=400;
bool game_end=0;
/////bullet////
float dx=0,dy=0;
float bull_speed=6;
float betta=0;
bool fl1=0, fl2=0;
/////ship////
float speed=0;
float angle=0;
float acsel=0;
/////asteroid/////
float ast_size=50;
float aster_speed=3;
/////0-rand////
int kol_aster=0;

class bullet
{
public:
	float dxb;
	float dyb;
	float angleb;
	bullet()
	{	dxb=dx;
		dyb=dy;
		angleb=betta;
	}
};

class asteroid
{
public:
	float anglea;
	float dx;
	float dy;
	float depth;
	int n;
	int i_big;
	int  ifsmall;
	vector <double> x;
	vector <double> y;
	void create(int i,bool param);
	void create_small(int i,int j,bool param,float depth1,float dx1,float dy1);

};

void asteroid:: create_small(int i,int j,bool param,float depth1,float dx1,float dy1)
	{
	
	ifsmall=0;
	int size=ast_size/2;
	depth=depth1+(j+2)*1.0/(8.0*(kol_aster));
	dx=dx1;
	dy=dy1;
	i_big=i;

	/////////////////////////////////////////////////

	int quat=rand()%4;
	int n1=rand()%2+1;
	int n2=rand()%2+1;
	int n3=rand()%2+1;
	int n4=rand()%2+1;
	n1=n2=n3=n4=1;
	n=n1+n2+n3+n4;
	double xi,yi;
	anglea=rand()%360;

	x.clear();
	y.clear();

	for (int i=0;i<n1;i++)
	{
		xi=rand()%(size/2)-size/2;
		yi=rand()%(size/2)+size/2;		
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n2;i++)
	{
		xi=rand()%(size/2)+size/2;
		yi=rand()%(size/2)+size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n3;i++)
	{
		xi=rand()%(size/2)+size/2;
		yi=rand()%(size/2)-size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n4;i++)
	{
		xi=rand()%(size/2)-size/2;

		yi=rand()%(size/2)-size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
	//////////////////////////////////////////////////

	}

void asteroid::  create(int kol_exist,bool param)
{
	int size=ast_size;
	int quat=rand()%4;
	int n1=rand()%2+1;
	int n2=rand()%2+1;
	int n3=rand()%2+1;
	int n4=rand()%2+1;
	n1=n2=n3=n4=1;
	n=n1+n2+n3+n4;
	double xi,yi;
	anglea=rand()%360;
	i_big=kol_exist;

	ifsmall=1;
	depth=(float)(kol_exist)/((kol_aster));
	dx=rand()%(int)winwid -winwid/2;
	dy=rand()%(int)winhei -winhei/2;
	if(quat==0) dy=-ast_size-winhei/2;
	if(quat==1) dy=ast_size+winhei/2;
	if(quat==2) dx=-ast_size-winwid/2;
	if(quat==3) dx=ast_size+winwid/2;

	x.clear();
	y.clear();

	for (int i=0;i<n1;i++)
	{
		xi=rand()%(size/2)-size/2;
		yi=rand()%(size/2)+size/2;		
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n2;i++)
	{
		xi=rand()%(size/2)+size/2;
		yi=rand()%(size/2)+size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n3;i++)
	{
		xi=rand()%(size/2)+size/2;
		yi=rand()%(size/2)-size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
	for (int i=0;i<n4;i++)
	{
		xi=rand()%(size/2)-size/2;

		yi=rand()%(size/2)-size/2;
		x.push_back(xi);
		y.push_back(yi);
	}
}

vector <bullet> vecb;
vector <asteroid> veca;

void destroy_small_ast( int i)
{
	//////если удалено 4 маленького-создать новый большой/////
	bool create_big=1;
	float up_boarder=(float)(veca[i].i_big)/((kol_aster));
	float down_boarder=(float)(veca[i].i_big)/((kol_aster));
	asteroid a_big;
	a_big.create(veca[i].i_big,1);
	if (i>0) if(veca[i-1].depth>down_boarder) create_big=0; 
	if (i<veca.size()-1) if(veca[i+1].depth<up_boarder) create_big=0;
	{if (create_big==1) 
	{veca.insert(veca.begin()+veca[i].i_big,a_big);
	veca[veca[i].i_big].create(veca[i].i_big,1);
	veca.erase(veca.begin()+i+1);}
	else veca.erase(veca.begin()+i);}
}

void destroy_aster(float dep)
{
	dep=1-2*dep;
	for(int i=0;i<veca.size();i++)
	{

		if (abs(dep-veca[i].depth)<0.0001) 	
			{if(veca[i].ifsmall==1) 
			{
				veca.resize(veca.size()+4);
				for(int j=0;j<4;j++)
					veca[veca.size()-j-1].create_small(i,j,0,veca[i].depth,veca[i].dx,veca[i].dy);
				veca.erase(veca.begin()+i);
				break;
			}
			else {destroy_small_ast( i);break;}
		}
	}
}

void shoot()
{
	float depth[5];
	for(int i=0;i<vecb.size();i++)
	{
		glLoadIdentity();
		//////пересчитали координаты//////
		vecb[i].dxb+=(speed+bull_speed)*cos(Pi*(vecb[i].angleb)/180.0);
		vecb[i].dyb+=(speed+bull_speed)*sin(Pi*(vecb[i].angleb)/180.0);
		////за пределами экрана/////
		if((vecb[i].dxb>winwid/2-1) ||(vecb[i].dxb<-winwid/2+1) ||(vecb[i].dyb<-winhei/2+1) || (vecb[i].dyb>winhei/2-1)) {vecb.erase(vecb.begin()+i);i--;}
		else{
			/////буффер глубины////
			glReadPixels((vecb[i].dxb+winwid/2),-vecb[i].dyb+winhei/2,2,2,GL_DEPTH_COMPONENT,GL_FLOAT,depth);
			if (depth[0]!=1)
			{
				destroy_aster(depth[0]);
				vecb.erase(vecb.begin()+i);
				i--;
			}
			else
			{
				//////нарисовали пулю//////
				glTranslatef(vecb[i].dxb,vecb[i].dyb,0.0f);	
				glColor3f(1.0f,1.0f,1.0f);
				glBegin(GL_LINES);
				glVertex3f( 0.0,0.0, 0.5f);
				glVertex3f(1.0,0.0, 0.5f);
				glEnd();
			}
		}
	}
}

void aster_draw()
{
	glColor3f(0.5f,1.0f,1.0f);
	glLoadIdentity();
	for (int i=0;i<veca.size();i++)
	{
		glBegin(GL_POLYGON);
		for(int j=0;j<veca[i].n;j++)
		glVertex3f( veca[i].dx+veca[i].x[j],veca[i].dy+veca[i].y[j], veca[i].depth);
		glEnd();
		veca[i].dx+=aster_speed*cos(Pi*(veca[i].anglea)/180.0);
		veca[i].dy+=aster_speed*sin(Pi*(veca[i].anglea)/180.0);
	/////за пределами окна маленькиц уничтожить, большой создать заново///
		if((veca[i].dx>winwid/2+ast_size) ||(veca[i].dx<-winwid/2-ast_size) ||(veca[i].dy<-winhei/2-ast_size) || (veca[i].dy>winhei/2+ast_size)) 
		if (veca[i].ifsmall==0)
		{destroy_small_ast( i);i--;}
		else veca[i].create(i,1);
	}
}

void asteroidsinit()
{
	int k;
	k=rand()%6+4;
	if(kol_aster!=0)	k=kol_aster;
	else  kol_aster=k;
	veca.resize(k);
	for(int i=0;i<k;i++)
		veca[i].create(i,1);
}

void draw_ship()
{

	float depth[6];
	float dx1,dx2,dy1,dy2;

	////////корабль пересекся с астероидом/////
	if ((dx<winwid/2-1)&&(dx>-winwid/2+1)&&(dy<winwid/2-1)&&(dy>-winwid/2+1))
		glReadPixels((dx+winwid/2),-dy+winhei/2,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,depth);
	else depth[0]=1;
	
	dx1=dx-10*cos(Pi*betta/180)-10*sin(Pi*betta/180)+winwid/2;
	dy1=-dy+10*sin(Pi*betta/180)-10*cos(Pi*betta/180)+winhei/2;
	if ((dx1<winwid-1)&&(dx1>0+1)&&(dy1<winhei-1)&&(dy1>0+1))
		glReadPixels(dx1,dy1,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,depth+1);
	else 
		depth[1]=1;
	dx2=dx-10*cos(Pi*betta/180)+10*sin(Pi*betta/180)+winwid/2;
	dy2=-dy+10*sin(Pi*betta/180)+10*cos(Pi*betta/180)+winhei/2;
	if ((dx2<winwid-1)&&(dx2>0+1)&&(dy2<winhei-1)&&(dy2>0+1))
		glReadPixels(dx2,dy2,1,1,GL_DEPTH_COMPONENT,GL_FLOAT,depth+2);
	else
		depth[2]=1;
	///////корабль за пределами экрана////
	if(dx>winwid/2) dx=-winwid/2;
	if(dx<-winwid/2) dx=winwid/2;
	if(dy<-winhei/2) dy=winhei/2;
	if(dy>winhei/2) dy=-winhei/2;

/////////рисуем//////
	glColor3f(0.8f,0.0f,0.8f);
	glLoadIdentity();
	glTranslatef(dx,dy,0.0f);	
	glRotatef(betta,0.0f,0.0f,1.0f);  			
	glBegin(GL_TRIANGLES);
	glVertex3f( -10.0f,-10.0f, 1.0f);
	glVertex3f(-10.0f,10.0f, 1.0f);
	glVertex3f(0.0f,0.0f, 1.0f);	
	if (fl2==1){
		glVertex3f( -10.0f,-3.0f, 1.0f);	
		glVertex3f(-10.0f,3.0f, 1.0f);	
		glVertex3f(-15.0f,0.0f, 1.0f);	
	}
	glEnd();
/////////корабль столкнулся-игра закончилась/////////
			if ((depth[0]!=1)||(depth[1]!=1)||(depth[2]!=1))	
				game_end=1;
}

void display() 
{ 
	glClearDepth( 1.0f );
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	aster_draw();
	draw_ship();
	shoot();
	glutSwapBuffers(); 
} 

void Timer(int)
{
	acsel--;
	if(speed>10) speed=10;	
	if (fl1==1) {angle=betta;fl1=0;}
	if (acsel==0) {fl2=0;}
	dx=dx+speed*cos(Pi*angle/180.0);
	dy=dy+speed*sin(Pi*angle/180.0);
	if(speed>0)speed=speed-0.1;
	else speed=0;
	display();
	if(game_end==0) glutTimerFunc(50,Timer,0);
}

void Initialize()
{
	dx=0;
	dy=0;
	vecb.empty();
	angle=betta=speed=0;
	glClearColor(0, 0, 0.0, 1.0); 
	glMatrixMode(GL_PROJECTION); 
	glLoadIdentity(); 
	glOrtho(-winwid/2, winwid/2, winhei/2, -winhei/2, -1, 1); 
	glMatrixMode(GL_MODELVIEW);
	glEnable(GL_DEPTH_TEST);
	glDepthFunc( GL_LEQUAL ); 
	float depth[5];
	glClearDepth( 1.0f );              // Разрешить очистку буфера глубины
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	asteroidsinit();
	glutTimerFunc(500,Timer,0);
}

void keyboard(unsigned char key,int x,int y)
{
	if (key=='w') {fl1=1;speed++;fl2=1;acsel=10;}
	if (key=='d') {betta+=7;}
	if (key=='a') betta-=7;
	if (key==' ') {bullet b1;vecb.push_back(b1);}
	if(key=='r') {if(game_end==1) {game_end=0;Initialize();}}

}

int main(int argc, char **argv)//Главная часть 
{ 

	glutInit(&argc, argv); 
	glutInitDisplayMode(GLUT_DEPTH |GLUT_DOUBLE | GLUT_RGB); 
	glutInitWindowSize(winwid, winhei); 
	glutInitWindowPosition(200, 200); 
	glutCreateWindow("Powder Toy"); 
	Initialize();
	glutDisplayFunc(display); 
	glutKeyboardFunc(keyboard);
	glutMainLoop(); 
}


game.cpp
#include "game.h"
#include "logic.h"

Game::Game(unsigned width, unsigned height)
    : _asteroids(std::vector<AsteroidFamily *>()), _shots(std::vector<Shot *>()), _booms(std::vector<Boom *>()),
      _score(0), _livesBonus(10000), _level(0), _isAsteroidsEmpty(true), _gameOver(false),
      _playerPoints(new std::vector<Point>(3)), _shotsPoints(new std::vector<Point>(4)),
      _boomPoints(new std::vector<Point>(8)), _lastTimepoint(std::chrono::high_resolution_clock::now()),
      _lastShotTimepoint(std::chrono::high_resolution_clock::now()),
      _gameOverTimepoint(std::chrono::high_resolution_clock::now()), _timeMultiplier(0.0f), _width(width),
      _height(height), _aspectRatio((float)width / (float)height),
      _render(new GL(&_aspectRatio, &_halfWidth, &_halfHeight)),
      _controls(new Controls(&_width, &_height, &_halfWidth, &_halfHeight)) {

    _halfHeight = GAME_HEIGHT;
    _halfWidth = _aspectRatio * _halfHeight;

    _playerPoints = new std::vector<Point>(3);
    (*_playerPoints)[0].x = -0.6f;
    (*_playerPoints)[0].y = -0.5f;
    (*_playerPoints)[1].x = -0.6f;
    (*_playerPoints)[1].y = 0.5f;
    (*_playerPoints)[2].x = 0.6f;
    (*_playerPoints)[2].y =  0.0f;
    _shotsPoints = new std::vector<Point>(4);
    (*_shotsPoints)[0].x = 0.02f;
    (*_shotsPoints)[0].y = 0.02f;
    (*_shotsPoints)[1].x = 0.02f;
    (*_shotsPoints)[1].y = -0.02f;
    (*_shotsPoints)[2].x = -0.02f;
    (*_shotsPoints)[2].y = -0.02f;
    (*_shotsPoints)[3].x = -0.02f;
    (*_shotsPoints)[3].y = 0.02f;
    _boomPoints = new std::vector<Point>(8);
    (*_boomPoints)[0].x = 0.1f;
    (*_boomPoints)[0].y = 0.1f;
    (*_boomPoints)[1].x = 0.5f;
    (*_boomPoints)[1].y = 0.4f;
    (*_boomPoints)[2].x = -0.1f;
    (*_boomPoints)[2].y = -0.2f;
    (*_boomPoints)[3].x = -0.5f;
    (*_boomPoints)[3].y = -0.4f;
    (*_boomPoints)[4].x = 0.2f;
    (*_boomPoints)[4].y = -0.1f;
    (*_boomPoints)[5].x = 0.5f;
    (*_boomPoints)[5].y = -0.5f;
    (*_boomPoints)[6].x = -0.1f;
    (*_boomPoints)[6].y = 0.2f;
    (*_boomPoints)[7].x = -0.5f;
    (*_boomPoints)[7].y = 0.5f;

    Shot::SetStaticPoints(_shotsPoints);
    Boom::SetStaticPoints(_boomPoints);
    Random::Init(&_halfWidth, &_halfHeight);

    _player = new Player(_playerPoints, 0.0f, 0.0f);
}

Game::~Game() {
    delete _player;
    delete _render;
    for (Shot *item : _shots)
        delete item;
    for (Boom *item : _booms)
        delete item;
    for (AsteroidFamily *item : _asteroids)
        delete item;
    delete _playerPoints;
    delete _shotsPoints;
    delete _boomPoints;
}

void Game::Refresh() {
	_controls->Refresh();
    if (_score >= _livesBonus) {
        _livesBonus += 10000;
        _player->SetLives(_player->GetLives() + 1);
    }
    if (_isAsteroidsEmpty) {
        _level++;
        for (AsteroidFamily *item : _asteroids)
            delete item;
        _asteroids.clear();
        for (unsigned i = 0; i < (_level + 1) * 2; ++i)
            _asteroids.push_back(Random::GenerateAsteroidFamily());
        _isAsteroidsEmpty = false;
    }
    _isAsteroidsEmpty = true;
    std::chrono::high_resolution_clock::time_point now = std::chrono::high_resolution_clock::now();
    auto time_span = std::chrono::duration_cast<std::chrono::nanoseconds>(now - _lastTimepoint).count();
    _timeMultiplier = (float)time_span / 16666666.67f;
    _lastTimepoint = now;

    if (_controls->GetHyperspace()) {
        if (!_gameOver) {
            Random::ChangePlayerCoords(_player);
            _controls->SetHyperspace(false);
        } else {
            if (std::chrono::duration_cast<std::chrono::milliseconds>(now - _gameOverTimepoint).count() >=
                    GAMEOVER_SCORE_TIME) {
                _player->SetCoord(0.0f, 0.0f);
                _player->SetAngle(0.0f);
                _player->SetLives(PLAYER_DEFAULT_LIVES);
                for (AsteroidFamily *item : _asteroids)
                    delete item;
                _asteroids.clear();
                _isAsteroidsEmpty = true;
                _score = 0;
                _level = 0;
                _livesBonus = 10000;
                _gameOver = false;
                _controls->SetHyperspace(false);
            }
        }
    }

    if (_player->GetIsGhost() && !_gameOver) {
        if (!_player->GetIsRendering()) {
            if (std::chrono::duration_cast<std::chrono::milliseconds>(now - _player->GetDeadTime()).count() >=
                    PLAYER_BLACKOUT_TIME) {
                _player->SetIsRendering(true);
            }
        }
        if (std::chrono::duration_cast<std::chrono::milliseconds>(now - _player->GetDeadTime()).count() >= PLAYER_GHOST_TIME) {
            _player->SetIsGhost(false);
        }
    }

    if (_player->GetLives() <= 0 && !_gameOver) {
        _gameOver = true;
        _gameOverTimepoint = now;
        _player->SetIsGhost(true);
        _player->Stop();
    }

    if (_player->GetIsRendering() && !_gameOver) {
        RefreshObjectCoord(_player);
        _player->Refresh(_controls->GetAngle(), _controls->GetAcceleration());
        if (_controls->GetShoot()) {
            if (std::chrono::duration_cast<std::chrono::milliseconds>(now - _lastShotTimepoint).count() >= NEXT_SHOT_TIME) {
                _shots.push_back(_player->GenerateShot());
                _lastShotTimepoint = now;
            }
        }
    }

    for (auto it = _shots.begin(); it != _shots.end();) {
        RefreshObjectCoord(*it);
        (*it)->Refresh(_timeMultiplier);
        if ((*it)->GetDistance() >= std::min(_halfHeight, _halfWidth) * 2 - 1.2f) {
            delete(*it);
            it = _shots.erase(it);
        } else {
            ++it;
        }
    }

    for (AsteroidFamily *item : _asteroids) {
        if (item->GetLarge()->GetIsRendering()) {
            _isAsteroidsEmpty = false;
            RefreshObjectCoord(item->GetLarge());
            item->GetLarge()->Refresh();
            if (!_player->GetIsGhost()) {
                if (isCollision(_player, item->GetLarge())) {
                    item->DestroyLarge();
                    _score += SCORE_LARGE;
                    ProcessCollision(_player, item->GetLarge());
                }
            }
            if (item->GetLarge()->GetIsRendering())
                for (auto it = _shots.begin(); it != _shots.end();) {
                    if (isCollision(*it, item->GetLarge())) {
                        delete(*it);
                        it = _shots.erase(it);
                        item->DestroyLarge();
                        _booms.push_back(new Boom(item->GetLarge()->GetCoord().x, item->GetLarge()->GetCoord().y));
                        _score += SCORE_LARGE;
                    } else {
                        ++it;
                    }
                }
        } else {
            if (item->GetFirstSmall()->GetIsRendering()) {
                _isAsteroidsEmpty = false;
                RefreshObjectCoord(item->GetFirstSmall());
                item->GetFirstSmall()->Refresh();
                if (!_player->GetIsGhost()) {
                    if (isCollision(_player, item->GetFirstSmall())) {
                        item->GetFirstSmall()->SetIsRendering(false);
                        _score += SCORE_SMALL;
                        ProcessCollision(_player, item->GetFirstSmall());
                    }
                }
            }
            if (item->GetSecondSmall()->GetIsRendering()) {
                _isAsteroidsEmpty = false;
                RefreshObjectCoord(item->GetSecondSmall());
                item->GetSecondSmall()->Refresh();
                if (!_player->GetIsGhost()) {
                    if (isCollision(_player, item->GetSecondSmall())) {
                        item->GetSecondSmall()->SetIsRendering(false);
                        _score += SCORE_SMALL;
                        ProcessCollision(_player, item->GetSecondSmall());
                    }
                }
            }
            for (auto it = _shots.begin(); it != _shots.end();) {
                bool isFirstCollision = false, isSecondCollision = false;
                if (item->GetFirstSmall()->GetIsRendering())
                    isFirstCollision = isCollision(*it, item->GetFirstSmall());
                if (item->GetSecondSmall()->GetIsRendering())
                    isSecondCollision = isCollision(*it, item->GetSecondSmall());
                if (isFirstCollision || isSecondCollision) {
                    delete(*it);
                    it = _shots.erase(it);
                    if (isFirstCollision) {
                        item->GetFirstSmall()->SetIsRendering(false);
                        _booms.push_back(new Boom(item->GetFirstSmall()->GetCoord().x, item->GetFirstSmall()->GetCoord().y));
                        _score += SCORE_SMALL;
                    }
                    if (isSecondCollision) {
                        item->GetSecondSmall()->SetIsRendering(false);
                        _booms.push_back(new Boom(item->GetSecondSmall()->GetCoord().x, item->GetSecondSmall()->GetCoord().y));
                        _score += SCORE_SMALL;
                    }
                } else {
                    ++it;
                }
            }
        }
    }

    for (auto it = _booms.begin(); it != _booms.end();) {
        (*it)->Refresh(_timeMultiplier);
        if ((*it)->GetDuration() >= BOOM_MAX_DURATION) {
            delete(*it);
            it = _booms.erase(it);
        } else {
            ++it;
        }
    }
}

void Game::RefreshObjectCoord(Object *object) {
    object->SetCoord(object->GetCoord().x + object->GetVelocity().x * _timeMultiplier,
                     object->GetCoord().y + object->GetVelocity().y * _timeMultiplier);
    if (object->GetCoord().x <= -_halfWidth) object->SetCoord(object->GetCoord().x + _halfWidth * 2, object->GetCoord().y);
    else if (object->GetCoord().x >= _halfWidth) object->SetCoord(object->GetCoord().x - _halfWidth * 2,
                object->GetCoord().y);
    if (object->GetCoord().y <= -_halfHeight) object->SetCoord(object->GetCoord().x,
                object->GetCoord().y + _halfHeight * 2);
    else if (object->GetCoord().y >= _halfHeight) object->SetCoord(object->GetCoord().x,
                object->GetCoord().y - _halfHeight * 2);
}

void Game::Render() {
    Refresh();
    _render->Clear();

    _render->RenderControls(_controls);

    _render->SetColor(OBJECTS_COLOR);
    if (_player->GetIsRendering() && !_gameOver) {
        if (_player->GetIsGhost())
            _render->SetColor(PLAYER_GHOST_COLOR);
        _render->RenderPlayer(_player);
    }

    if (_gameOver)
        _render->SetColor(OBJECTS_GAMEOVER_COLOR);
    else
        _render->SetColor(OBJECTS_COLOR);

    for (AsteroidFamily *item : _asteroids) {
        if (item->GetLarge()->GetIsRendering()) {
            _render->RenderAsteroid(item->GetLarge());
        } else {
            if (item->GetFirstSmall()->GetIsRendering()) {
                _render->RenderAsteroid(item->GetFirstSmall());
            }
            if (item->GetSecondSmall()->GetIsRendering()) {
                _render->RenderAsteroid(item->GetSecondSmall());
            }
        }
    }

    for (Shot *item : _shots) {
        _render->RenderShot(item);
    }

    _render->SetColor(BOOM_COLOR);
    for (Boom *item : _booms) {
        _render->RenderBoom(item);
    }

    _render->SetColor(TEXT_COLOR);
    if (!_gameOver) {
        _render->RenderScoreAndLives(_score, _player->GetLives());
    } else {
        _render->RenderGameOver(_score);
    }
}

bool Game::isCollision(Player *player, Asteroid *asteroid) {
    const std::vector<Point> &playerPoints = *(player->GetPoints());
    const std::vector<Point> &asteroidPoints = *(asteroid->GetPoints());
    if (TestAABB(player, asteroid)) {
        for (unsigned i = 0; i < playerPoints.size(); i++) {
            for (unsigned j = 0; j < asteroidPoints.size(); j++) {
                if (Logic::IsLinesCross(playerPoints[i], playerPoints[(i + 1 == playerPoints.size()) ? 0 : i + 1],
                                        asteroidPoints[j], asteroidPoints[(j + 1 == asteroidPoints.size()) ? 0 : j + 1])) {
                    return true;
                }
            }
        }
        if (Logic::IsInside(asteroidPoints, playerPoints[0])) {
            return true;
        }
    }
    return false;
}

bool Game::isCollision(Shot *shot, Asteroid *asteroid) {
    if (Logic::IsInside(*(asteroid->GetPoints()), shot->GetCoord()))
        return true;
    else
        return false;
}

bool Game::TestAABB(Player *player, Asteroid *asteroid) {
    return (player->GetSizes()[0] < asteroid->GetSizes()[1] && player->GetSizes()[1] > asteroid->GetSizes()[0] &&
            player->GetSizes()[2] < asteroid->GetSizes()[3] && player->GetSizes()[3] > asteroid->GetSizes()[2]);
}

void Game::ProcessCollision(Player *player, Asteroid *asteroid) {
    _booms.push_back(new Boom(asteroid->GetCoord().x, asteroid->GetCoord().y));
    player->SetIsRendering(false);
    player->SetIsGhost(true);
    player->SetLives(player->GetLives() - 1);
    player->SetCoord(0.0f, 0.0f);
    player->SetDeadTime(std::chrono::high_resolution_clock::now());
}

void Game::Resize(float width, float height) {
    _aspectRatio = (float)width / (float)height;
    _halfWidth = _aspectRatio * _halfHeight;
    _width = width;
    _height = height;
    _render->Resize();
}

Controls *Game::GetControls() {
    return _controls;
}

bool Game::GetIsPaused() {
	return _isPaused;
}

void Game::SetIsPaused(bool isPaused) {
	_isPaused = isPaused;
}


Game.cpp
#include <Game.h>
#include <Controls.h>

#include <tuple>

Game::Game() {
    isLevelRunning = true;

    ResetLogic();
    RequestRestart();

    Renderer::InitInternals();
    Controls::Init();
    Score::Init();
}

Game& Game::Get() {
    static Game instance;
    return instance;
}

void Game::Restart() {
    objects.clear();
    Score::OnRestart();
    ResetLogic();
    GameObject::Create<Ship>();
    SpawnAsteroids(Constant::asteroidTargetCount);
}

//Внутри управляем рестартом, а наружу выдаем текущее состояние уровня (false - на паузе)
bool Game::IsLevelRunning(float dt) {
    if(wantRestart) {
        if(restartTimer < 0.0) {
            if(isLevelRunning) {
                Restart();
                wantRestart = false;
            }
        } else {
            restartTimer -= dt;
        }
    }
    return isLevelRunning;
}

void Game::Update() {
    float deltaTime = timer.Tick();

    if(IsLevelRunning(deltaTime)) {
        for(auto& go : objects) {
            go->Update(deltaTime);
        }

        DetectCollisions(deltaTime);

        DestroyRequestedObjects(); //Удаление объектов предполагается только здесь
    }

    Renderer::Draw();
}

void Game::OnGLInit() {
    Renderer::InitGLContext();
}

void Game::OnResolutionChange(int w, int h) {
    Renderer::OnResolutionChange(w, h);
    Controls::Resize();
    Score::Resize();
}

GameObject& Game::AddGameObject(std::unique_ptr<GameObject> obj) {
    objects.push_back(std::move(obj));
    return *objects.back().get();
}

void Game::DestroyRequestedObjects() {
    for(auto i = objects.begin(); i != objects.end();) {
        if((*i)->isDestructionRequested()) {
            i = objects.erase(i);
        } else {
            ++i;
        }
    }
}

void Game::DetectCollisions(float dt) {
    for(auto a = objects.begin(); a != objects.end(); ++a) {
        for(auto b = std::next(a); b != objects.end(); ++b) { //Для каждой пары объектов
            GameObject& ra = **a;
            GameObject& rb = **b;
            if(CollisionMask(ra, rb)) { //Требуется ли обработка столкновения
                if(DetectCollision(ra, rb, dt)) { //Базовый алгоритм
                    if(RefineCollision(ra, rb, dt)) { //Более точный
                        ra.OnCollision(rb);
                        rb.OnCollision(ra);
                    }
                }
            }
        }
    }
}


bool Game::CollisionMask(const GameObject& a, const GameObject& b) {
    //Если один из объектов логически уже уничтожен, то он не сталкивается с другими (return false)
    return !(a.isDestructionRequested() || b.isDestructionRequested()) &&
    //Если ни одному из объектов не требуется обработка столкновения с другим, то возвращаем false
    (a.CollisionMask(b.getStaticType()) || b.CollisionMask(a.getStaticType()));
}

//Обнаружение столкновений по радиусу окружности, описывающей модель объекта
//В непрерывном случае радиус расширяется на расстояние, которое объекты могут пройти за время dt
bool Game::DetectCollision(const GameObject& a, const GameObject& b, float dt) {
    if(Constant::continuousCollisions) {
        return (a.getPosition() - b.getPosition()).getLength() <
            a.getRadius() + b.getRadius() + (a.getVelocity().getLength() + b.getVelocity().getLength()) * dt;
    } else {
        return (a.getPosition() - b.getPosition()).getLength() < a.getRadius() + b.getRadius();
    }
}

bool Game::RefineCollision(const GameObject& a, const GameObject& b, float dt) {
    if(Constant::refineCollisions) {
        const Model& am = a.getModel();
        const std::vector<GLfloat>& av = am.getTransformed();
        const std::vector<GLubyte>& ai = am.getIndices();
        const Vec2 aBackVel = a.getVelocity() * -1;
        const Model& bm = b.getModel();
        const std::vector<GLfloat>& bv = bm.getTransformed();
        const std::vector<GLubyte>& bi = bm.getIndices();
        const Vec2 bBackVel = b.getVelocity() * -1;

        //Обработка для каждой пары отрезков, из которых состоит модель объекта
        for(int i = 0; i < ai.size(); i += 2) {
            Vec2 a0(i, av, ai);
            Vec2 at = Vec2(i + 1, av, ai) - a0;
            for(int j = 0; j < bi.size(); j += 2) {
                Vec2 b0(j, bv, bi);
                Vec2 bt = Vec2(j + 1, bv, bi) - b0;
                if(Constant::continuousCollisions ?
                    //Алгоритм считает, что отрезки передаются в момент времени t0,
                    //но наши отрезки уже в t0+dt, поэтому передаем скорости со знаком -
                    MovingSegmentCollision(a0, at, aBackVel, b0, bt, bBackVel, dt) :
                    SegmentCollision(a0, at, b0, bt)) return true;
            }
        }
        return false;
    } else {
        return true;
    }
}

bool Game::SegmentCollision(Vec2 p, Vec2 r, Vec2 q, Vec2 s) {
    //http://stackoverflow.com/a/565282/2502024
    float det = Vec2::CrossProd2D(r, s);
    if(fabs(det) > Constant::smallNumber) {
        Vec2 diff = q - p;
        float f = Vec2::CrossProd2D(diff, s / det);
        float g = Vec2::CrossProd2D(diff, r / det);
        return f >= 0 && f <= 1 && g >= 0 && g <= 1;
    }
    return false;
}

bool Game::MovingSegmentCollision(Vec2 p, Vec2 r, Vec2 vp, Vec2 q, Vec2 s, Vec2 vq, float dt) {
    float det = Vec2::CrossProd2D(r, s);
    if(fabs(det) > Constant::smallNumber) {
        const Vec2 v = vq - vp;
        const Vec2 diff = q - p;
        //Расширение предыдущего алгоритма с учетом:
        //q = q0 + v*t, t in [0, dt]
        //(v.x * s.y - v.y * s.x) * t + ((q.x - p.x) * s.y - (q.y - p.y) * s.x)

        //Точки пересечения f и g из SegmentCollision теперь зависят от t.
        //Отрезки пересекаются в точке t из [0, dt], если найдется такое t,
        //что f и g одновременно лежат в [0, 1]. Т.е. решаем 3 пары неравенств относительно t
        auto getInequation = [=](Vec2 dir)->std::tuple<float, float> {
            //0 <= a*t + cp <= 1
            float cp = Vec2::CrossProd2D(diff, dir / det);
            float a = Vec2::CrossProd2D(v, dir / det);
            float left = -cp, right = 1 - cp;
            if(fabs(a) < Constant::smallNumber) {
                if(cp >= 0 && cp <= 1) {
                    left = 0;
                    right = dt;
                } else {
                    left = dt + 1;
                    right = -1;
                }
            } else {
                left /= a;
                right /= a;
                if(a < 0) std::swap(left, right);
            }
            return std::make_tuple(left, right);
        };

        float ls, rs, lr, rr;
        //ls <= t <= rs
        std::tie(ls, rs) = getInequation(s);
        //lr <= t <= rr
        std::tie(lr, rr) = getInequation(r);

        //одновременно с 0 <= t <= dt
        float mx = std::max(0.f, std::max(ls, lr));
        float mn = std::min(dt, std::min(rs, rr));
        return mx <= mn;
    }
    return false;
}

void Game::RequestRestart(float t) {
    wantRestart = true;
    restartTimer = t;
}

void Game::Pause() {
    isLevelRunning = false;
    Controls::onPause();
}

void Game::Resume() {
    isLevelRunning = true;
    Controls::onResume();
    timer.Tick();
}

void Game::SetPlayerPos(const Ship& player) {
    playerPos = player.getPosition();
}

Vec2 Game::GetPlayerPos() {
    return playerPos;
}

void Game::AddPoints(int pointsToAdd) {
    Score::AddPoints(pointsToAdd);
}

void Game::DecAsteroidCount(const Asteroid& a) {
    asteroidCount--;
    if(asteroidCount == Constant::asteroidUfoCount * 2 && !isUfoPresent) {
        GameObject::Create<UFO>(GetUfoSpawn());
    }
    if(asteroidCount <= Constant::asteroidRespawnCount * 2) {
        SpawnAsteroids(Constant::asteroidTargetCount - Constant::asteroidRespawnCount);
    }
}

//Увеличиваем на 2, т.к. asteroidCount считаем по половинам большого астероида
void Game::IncAsteroidCount(const Asteroid& a) {
    asteroidCount += 2;
}

void Game::ResetLogic() {
    asteroidCount = 0;
    isUfoPresent = false;
}

void Game::SpawnAsteroids(int n) {
    for(int i = 0; i < n; ++i) {
        GameObject::Create<Asteroid>(GetSpawnPosition());
    }
}

//Создаем астероид так, чтобы сразу не убить игрока (с учетом зацикленности игровых координат)
Transform Game::GetSpawnPosition() {
    std::uniform_real_distribution<float> zone(-Constant::asteroidSpawnZone, Constant::asteroidSpawnZone);
    Vec2 pos(Constant::worldRatio + 0.2, 1.2);
    if(fabs(playerPos.x) > Constant::asteroidSpawnZone &&
         fabs(playerPos.y) < Constant::asteroidSpawnZone) {
        pos.y = zone(Random::generator);
    } else if(fabs(playerPos.x) < Constant::asteroidSpawnZone &&
                fabs(playerPos.y) > Constant::asteroidSpawnZone) {
        pos.x = zone(Random::generator);
    } else {
        if(Random::flipCoin()) {
            pos.x = zone(Random::generator);
        } else {
            pos.y = zone(Random::generator);
        }
    }
    return Transform(pos);
}

Transform Game::GetUfoSpawn() {
    std::uniform_real_distribution<float> zone(-Constant::ufoZone, Constant::ufoZone);
    return Transform((Constant::worldRatio + 0.12) * (playerPos.x > 0 ? -1 : 1), zone(Random::generator));
}

void Game::OnUfoCreated(const UFO& u) {
    isUfoPresent = true;
}

void Game::OnUfoDestroyed(const UFO& u) {
    isUfoPresent = false;
}


model_handler.cpp
#include "model_handler.h"

#include <time.h>
#include <math.h>
#include <cstdlib>

using namespace model;

namespace {
    const double tickTime = 40.00;

    const unsigned int asteroidNumber = 8;
    const float projectileSpeed = 10.0;

    const float smallAsteroidRadiusK =  1.5;
    const float minLargeAsteroidRadius = 35.0;
    const float maxLargeAsteroidRadius = minLargeAsteroidRadius * smallAsteroidRadiusK - 1.0;
    const float minAsteroidSpeed = 1.5;
    const float maxAsteroidSpeed = 6.5;

    const float explosionK = 50000.0;

}

ModelHandler::ModelHandler(float worldWidth, float worldHeight):
    _isGameOver(false),
    _worldWidth(worldWidth),
    _worldHeight(worldHeight),
    _tickTime(0),
    _ship(ShipPtr(new Ship(Point(worldWidth / 2.0, worldHeight / 2.0)))) {

    srand(time(0));
}

void ModelHandler::newGame() {
    _asteroids.clear();
    _projectiles.clear();
    _ship.reset(new Ship(Point(_worldWidth / 2.0, _worldHeight / 2.0)));
    _isGameOver = false;
}

bool ModelHandler::isGameOver() const {
    return _isGameOver;
}

void ModelHandler::update(double deltaTime) {
    if (this->isGameOver()) return;

    _tickTime += deltaTime;
    while (_tickTime > tickTime) {

        if (_asteroids.size() < ::asteroidNumber) {
            this->addAsteroid();
        }

        for (ObjectPtr& obj: this->allObjects()) {
            obj->move();
        }

        this->checkObjects(&_asteroids);
        this->checkObjects(&_projectiles);

        if (!this->withinBoundaries(_ship)) {
            this->removeShip();
        }

        _tickTime -= tickTime;
    }
}

ShipPtr ModelHandler::ship() const {
    return _ship;
}

void ModelHandler::removeShip() {
    _isGameOver = true;
}

void ModelHandler::removeAsteroid(const AsteroidPtr& asteroid) {
    if (asteroid->collisionRadius() >= ::minLargeAsteroidRadius) {

        const model::Vector v1(asteroid->velocity()
                               + model::Vector(-asteroid->velocity().y, asteroid->velocity().x));
        const model::Vector v2(asteroid->velocity()
                               + model::Vector(asteroid->velocity().y, -asteroid->velocity().x));

        this->addAsteroid(asteroid, v1);
        this->addAsteroid(asteroid, v2);
    }
    _asteroids.remove(asteroid);
}

void ModelHandler::addAsteroid(const AsteroidPtr& asteroid) {
    _asteroids.push_back(asteroid);
}

std::list<AsteroidPtr> ModelHandler::asteroids() const {
    return _asteroids;
}

std::list<ProjectilePtr> ModelHandler::projectiles() const {
    return _projectiles;
}

void ModelHandler::removeProjectile(const ProjectilePtr& projectile) {
    _projectiles.remove(projectile);
}

void ModelHandler::addProjectile() {
    Vector projectileSpeed = _ship->direction() * ::projectileSpeed + ship()->velocity();
    _projectiles.push_back(ProjectilePtr(new Projectile(_ship->point(), projectileSpeed)));
}

void ModelHandler::processHit(const ProjectilePtr& projectile, const AsteroidPtr& asteroid) {
    if (asteroid->collisionRadius() >= ::minLargeAsteroidRadius) {
        const Vector ox = asteroid->velocity().normaVector();
        Vector explosionVector(ox.y, -ox.x);

        if (ox * asteroid->velocity() < 0) {
            explosionVector = explosionVector * (-1.0);
        }

        const Vector v1(asteroid->velocity() + model::Vector(-asteroid->velocity().y, asteroid->velocity().x)
                        + explosionVector * (-::explosionK / asteroid->mass()));
        const Vector v2(asteroid->velocity() + model::Vector(asteroid->velocity().y, -asteroid->velocity().x)
                        + explosionVector * (::explosionK / asteroid->mass()));

        this->addAsteroid(asteroid, v1);
        this->addAsteroid(asteroid, v2);
    }
    _projectiles.remove(projectile);
    _asteroids.remove(asteroid);
}

std::list<ObjectPtr> ModelHandler::allObjects() const {
    std::list<ObjectPtr> objects;
    objects.insert(objects.end(), _asteroids.begin(), _asteroids.end());
    objects.insert(objects.end(), _projectiles.begin(), _projectiles.end());
    objects.push_back(_ship);
    return objects;
}

void ModelHandler::addAsteroid() {

    const float r = common::rangeRand(::minLargeAsteroidRadius, ::maxLargeAsteroidRadius);

    Point point;
    bool isCorrect = false;
    while (!isCorrect) {
        point = randPoint(r);
        isCorrect = true;
        for (const AsteroidPtr& asteroid : _asteroids) {
            const float d = model::distance(asteroid->point(), point);
            if (d < (asteroid->collisionRadius() + r)) {
                isCorrect = false;
                break;
            }
        }
    }

    const float distToCenter = ::distance(point.x, point.y, _worldWidth / 2.0, _worldHeight / 2.0);
    const float vx = (_worldWidth / 2.0 - point.x) / distToCenter
            * common::rangeRand(::minAsteroidSpeed, ::maxAsteroidSpeed);
    const float vy = (_worldHeight / 2.0 - point.y) / distToCenter
            * common::rangeRand(::minAsteroidSpeed, ::maxAsteroidSpeed);

    _asteroids.push_back(AsteroidPtr(new Asteroid(point, r, Vector(vx, vy))));
}

void ModelHandler::addAsteroid(const AsteroidPtr& oldAsteroid, const Vector& newVelocity) {
    Point point = oldAsteroid->point();
    point.move(newVelocity.normaVector() * oldAsteroid->collisionRadius());
    _asteroids.push_back(AsteroidPtr(new Asteroid(point, oldAsteroid->collisionRadius()
                                                  / ::smallAsteroidRadiusK, newVelocity)));
}

Point ModelHandler::randPoint(float r) const {
    float x = 0;
    float y = 0;
    switch (rand() % 4) {
    case 0:
        x = common::rangeRand(0 - r, _worldWidth + r);
        y = 0 - r;
        break;
    case 1:
        x = common::rangeRand(0 - r, _worldWidth + r);
        y = _worldHeight - r;
        break;
    case 2:
        x = 0 - r;
        y = common::rangeRand(0 - r, _worldHeight + r);
        break;
    case 3:
        x = _worldWidth + r;
        y = common::rangeRand(0 - r, _worldHeight + r);
        break;
    default:
        break;
    }

    return Point(x, y);
}

bool ModelHandler::withinBoundaries(const ObjectPtr& obj) const {
    return (obj->x() > (0 - _worldWidth * 0.1) && obj->x() < (_worldWidth * 1.1)
            && obj->y() > (0 - _worldHeight * 0.1) && obj->y() < (_worldHeight * 1.1));
}

template<class T> void ModelHandler::checkObjects(std::list<T>* objects) {
    typename std::list<T>::iterator it = objects->begin();
    while (it != objects->end())     {
        if (!this->withinBoundaries(*it)) {
            it = objects->erase(it++);
        } else {
            ++it;
        }
    }
}



На мой взгляд, среди перечисленных тестовых заданий только одного немного выделяется. Всех авторов мы позвали на собеседование. Сможете угадать, чем один кандидат отличался от остальных? Для меня это почти очевидно, когда я вижу очередное тестовое, но друзья не верят.
Автор: @viktorkorsun
ZeptoLab
рейтинг 48,72
Похожие публикации

Комментарии (62)

  • +3
    Сможете угадать, чем один кандидат отличался от остальных?

    «model_handler.cpp» архитектурным мышлением?
    • 0
      Хорошее архитектурное мышление было не только у этого кандидата
      • +3
        Надо было добавить в статью голосование за лучший код :)
      • –1
        >Хорошее архитектурное мышление было не только у этого кандидата
        Может у кандидата и было архитектурное мышление, но код его вызывает ужас. Хочется взять и переписать.

        Считаю также, что при написании Zeptolab-овского кода (был знаком с ним не понаслышке) «хорошее архитектурное мышление» применялось чуть чаще чем никогда, а во фреймворке в ряде мест было UD по стандарту.
        Но ведь главное, что компилятор хавает и все работает :)
        • 0
          UD UB
        • +1
          Дмитрий, бесспорно, ошибки в коде у нас есть. Мало того, я думаю, что в некотором количестве они будут в коде компании всегда. Но в то же время я считаю, что качество кода и технических решений у нас — на высочайшем уровне, и оно только повышается от проекта к проекту.

          Другой вопрос, что каждый показывает себя. Мне жаль, что про время нашей совместной работы сейчас ты вспомнил только несколько мест во фреймворке с UB, которые «схавал» компилятор.
          • 0
            про время нашей совместной работы сейчас ты вспомнил только несколько мест во фреймворке

            Про свое время работы в Zeptolab помню все до мельчайших подробностей и с ужасом вспоминаю до сих пор.
            Но было и прекрасное: например, холодильник и шкаф с едой. Они настолько волшебны, что больше месяца не позволяли мне уволиться :)
  • +2
    Я знаю, чем точно выделяется один файл — в Game.cpp есть читаемые комментариии

    P.s. а еще бросается в глаза код-стиль, но я не на С++
  • +12
    кандидат — Game.cpp? мне он отличился даже не комментариями, а тем, что все процедуры на страничку умещаются + стиль
  • 0
    Только у одного комментарии к коду.
    • 0
      В самом первом, который на Glut, тоже есть комменты (вероятно, кодировка попорчена).

      Но тот, который Game.cpp, и вправду очень неплохо откомментирован: методы короткие и простые — не откомментированы в стиле «а здесь мы в переменную c запишем сумму переменных a + b», а в более сложных — комментарий присутствует.
      • 0
        кодировку поправил, спасибо
      • 0
        Имена методов неудачные.
        Тот же откомментированный «IsLevelRunning» делает не то, что написано в его имени. Это скорее «VerifyIsLevelsRunning» или как-то так. Если бы имя было правильное — комментарий был бы не нужен.
        • 0
          Давайте прикинем, чуть-чуть:
          ЕслиУровеньЗапущен
          ПроверитьЕслиУровеньЗапущен

          Не понимаю чем ваше именование удачнее автора кода?
          По факту оно даже хуже, т.к. длиннее, но при этом не добавляет смысловой нагрузки.

          В том же ruby можно юзать "?" в именах методов и там считается хорошим стилем методы возвращающие true/false запаковывать в имена типа «empty?» тут такой возможности как я понимаю нет, поэтому используется вопросительный стиль IsBlaBla?, но без знака '?'
          • 0
            Вообще Krypt прав, так как метод совсем не отвечат принципу Single Responsibility, что чревато сложной расширяемостью и прочими недостатками. Если я вижу метод IsXXX, это значит, что метод проверит состояние и вернет результат, больше ничего.
            Тут же корректным (да и то не полностью) названием было бы UpdateRestartTimerAfterRestartLevelIfNeedAndReturnIsLevelRunningState(), некрасиво как-то.
            Даже комментарий не зря автор кода оставил, так как метод внутри непрозрачный и название несоответствует действию.

            Код метода, чтобы не скроллить по многу раз к классу Game.cpp
            //Внутри управляем рестартом, а наружу выдаем текущее состояние уровня (false - на паузе)
            bool Game::IsLevelRunning(float dt) {
                if(wantRestart) {
                    if(restartTimer < 0.0) {
                        if(isLevelRunning) {
                            Restart();
                            wantRestart = false;
                        }
                    } else {
                        restartTimer -= dt;
                    }
                }
                return isLevelRunning;
            }
            
            • 0
              Я с тобой абсолютно согласен на все 146%, но согласись что твой коммент и Krypt всё же сильно разные и именно его VerifyIs от Is ничем не отличается кроме длины, что в принципе не имеет смысла.
              • 0
                Да, я наверное вник в суть вашего спора лишь поверхностно, потому и мой комментарий такой.

                К тому же, не знал про такую интересную особенность ruby, спасибо.
    • 0
      Во втором тоже есть
  • +10
    Game.cpp — нет одинаковых кусков кода, во всех остальных увидел, что половину можно вынести в функции)
  • +4
    Так как спасли жизни то?

    Если считать 20 загрузок игры за некоторый базовый показатель, мне кажется, спасено этим минимум полсотни жизней.
    А если совсем удалить игру из сторов, тогда еще больше спасете жизней (сарказм, троллинг)

    Просто если люди не будут тратить время на вашу игру, значит они будут тратить время на другую. То же самое касается времени загрузки — сократили время загрузки, значит пользователь будет на 9 секунд больше играть в вашу игру, а может даже больше, т.к. ему не так быстро надоест загрузки уровня.

    Пс: обожаю зеленого голодного монстра
    • 0
      Да, учитывая суммарное количество установок (больше 500 миллионов) и игровых сессий, набирается внушительное время, которое пользователи перестали тратить на ожидание загрузки уровня.

      Если это время потратить на игровой процесс, оно не будет бесцельно прожитым :)
  • +1
    Хм, забавно.
    Автор model_handler знает про дублирование констант при компиляции и поэтому завернул их в namespace. Но ведь это cpp-файл, он не будет include-ится много раз. Может это кто-нибудь объяснить мне, новичку в C++, зачем?
    • +6
      Безымянные namespace нужны, чтобы символы не «торчали» наружу этого модуля трансляции.
      Для этой же цели можно использовать ключевое слово static. Однако, у него есть еще несколько значений, поэтому рекомендуется все-таки использовать безымянные namespace.
    • +4
      namespace-scope константы имеют internal linkage по-умолчанию, если нигде не имеется extern declaration на них, так что это лишнее.
  • +4
    Относительно кандидатов — зависит от того в какую сторону «отличается» кандидат, в выгодную или нет. Я каждое решение могу выделить на фоне остальных:
    1. Напоминает мне о JS напиханностью кода в одну строчку.
    2. 100% студент или школьник («лабораторную работу» напоминает)
    3. Python стиль — подчëркивания в начале имени переменной и конструктор инициализирующий как-то слишком много всего (не характерно для Python, но что-то есть).
    4. Ruby? — не могу описать впечатление, скорее просто из-за вложенности и использования лямда-функции
    5. Сишник, который больше всех похож на С++, но в последнем методе сдался и написал на С (указатель на list) :)
  • +5
    Game.cpp. Намного лучше знает о C++11. Это видно по использованию: использование генератора случайных чисел из STL(это лучше rand), auto, кортежи, лямбда функции.
    • 0
      А про remove_if не знает, и auto можно было использовать более эффективно.
  • +2
    Похоже, что это новый вариант вступительного задания от zeptolab)
  • 0
    Про каждого кандидата из перечисленных можно сказать, что он что-то знает лучше или хуже остальных. Но один из кандидатов отличается в реальном мире от остальных. Подсказка: образование и возраст всех кандидатов примерно одинаковые.
    • +6
      Девушка? =)
      • +7
        Бинго! Осталось найти исходник
        • 0
          Склоняюсь к Game.cpp, поскольку девочки более опрятные чем мальчики как и этот исходник
        • +1
          Второй?
          • 0
            да
            • +3
              Неужели стиль комментариев и орфографические ошибки ее выдают? :)
              • +2
                Семантически тоже есть интересные отличия
                • +1
                  Нет никакой последовательности. Функции есть написанные слитно и через подчёркивание, с маленькой и большой буквы. Где-то отступы одни, где-то другие.
              • +2
                Это хороший аргумент, если не хочется никого обидеть.

                Код отличается общим невысоким качеством: куча глобальных переменных, классы с открытыми данными, единственный const на весь приведенный код.
              • 0
                Как намекнули на пол — через воспоминание сразу подумал на искомого автора\
            • +7
              //////если удалено 4 маленького-создать новый большой/////
                  bool create_big=1;
              

               glClearDepth( 1.0f );              // Разрешить очистку буфера глубины
              

              /////////корабль столкнулся-игра закончилась/////////
                          if ((depth[0]!=1)||(depth[1]!=1)||(depth[2]!=1))	
                              game_end=1;
              

              Все комментарии очевидны.
              Хотел сказать, не хватает только init // Инициализация, но тут есть:

              int main(int argc, char **argv)//Главная часть
              

            • 0
              «для полета коробляб» — не очень-то грамотная и внимательная девушка.
              • 0
                На мой взгляд, по одной опечатке не стоит судить так строго
                • +1
                  //////если удалено 4 маленького-создать новый большой/////
                  • +1
                    Имея синдром острого перфекционизма, очень болезненно воспринимаю тире, не обрамленное пробелами.
                    Кроме того, дико режет глаз «непостоянство» форматирования кода, например в списке параметров при вызове функции:

                    glVertex3f( 0.0,0.0, 0.5f);
                    
                    

                    Левая скобка отделена пробелом от параметров, правая — нет. После первой запятой нет пробела, после второй — есть.
            • 0
              Потому что это классика разработчика, а не кодера-задрота.
              Простой, понятный код, АЛГОРИТМА для команды
              Именно такого плана программистов и нанимает google.
    • +2
      Один из кандидатов — девушка и в коде это как-то просматривается. Я wannabe-программист для Arduino, но, полагаю, что этот вывод следует из ваших слов.
  • +1
    Единственный человек включает свои файлы через #include <>, очевидно он знает про флажок компилятора -I, возможно умеет пользоваться системами сборки.
  • +1
    Game.cpp — какой-то код красивый, в смысле форматирования. Плюс комментарии, которые туда органично вписаны.
    З.Ы. В код не вникал, я полугуманитарий.
  • +15
    Это на грани индусского кода:
    if (Logic::IsInside(*(asteroid->GetPoints()), shot->GetCoord()))
        return true;
    else
        return false;
    

    Вместо:
    return Logic::IsInside(*(asteroid->GetPoints()), shot->GetCoord())
    
    • +1
      Я с вами согласен, но есть противоположное мнение у некоторых уважаемых людей

      http://avva.livejournal.com/2633281.html
      </necromant mode>
  • +5
    Game.cpp мне наиболее симпатичен. Сразу выделяется на фоне остальных.
  • 0
    Сложно считать идеальным хотя бы одно решение.
    Везде есть плюсы и минусы.
    Что удивило что только в 2х решениях в цикл апдейта передается FrameDeltaTime. (без этого сложно делать такое как «пауза», «ускорение»\«замедление» игры).
    И только в одном решении используется фиксированный шаг для апдейта. (В принципе можно без него — но сложно задачи для расчета непрерывной коллизии будет выше и просмотрев мельком код я нигде этого в полной мере не заметил).
    В целом именно по коду положительно выделяются 2 решения. Но и там и там есть мелкие придирки.
    В идеальном вариенте в главном цикле не должно быть аллокаций — те если вдруг геймдизайнер или художник захочет увеличить кол-во объектов — игра может потерять плавность. (ну и вообще удаление за линейное время это странно!).
  • +1
    Хотя я с С++ дружу не очень, но предпочтение отдал бы Game.cpp —
    • Нету magic numbers
    • Нету лишних include блоков
    • Используются возможности С++11
    • Методы краткие, в них все понятно
    • Приятный code-style, все четко и красиво
  • +2
    А вот кстати ссылка на доклад, с которым автор поста выступит у нас на конференции Мобиус!
  • +1
    Второй кандидат. Это С программист. Глобальные переменные, классы — которые не классы, а примитивные структуры с публичными данными (попытки написать методы не в счет), и все написано функциями.
  • +6
    Мой взгляд, далекой от программирования девушки:
    Первый — я хз что это, ни чего не поняла и читать сложно = «дочитала до конца строки забыла что начало было»… и это
    Второй — кандидат явно девушка, по количеству слешей заметно… «и маленького» и типа «нарисовали пулю» мужчины, такое в комментах использовать не будут. Код не аккуратный, на мой взгляд грязноват. И это const float Pi=3.14159265358; мне кажется не правильно…
    Третий — лучше, чем предыдущий но стиль страдает, но тоже страдает длинннннными переменными или чем там… вообщем ну так се…
    Четвертый — молодец, приятно читать, даже ссылка на стак есть.
    Кроме 2 и 4 все используют std::(что-то там)… я честно прогуглила, это вроде из плюсов, а плюсы меня пугают)
    • +1
      Про девушку угадали верно! А как же пятый кандидат?
      • +1
        Пятый видимо давно фрилансит), потому что код без пояснений, явно не в команде. И вот это убило мой мозг:
        bool ModelHandler::withinBoundaries(const ObjectPtr& obj) const {
            return (obj->x() > (0 - _worldWidth * 0.1) && obj->x() < (_worldWidth * 1.1)
                    && obj->y() > (0 - _worldHeight * 0.1) && obj->y() < (_worldHeight * 1.1));
        

        мне кажется не культурно такие записи не пояснять, это как… «о дивный новый мир», там такой же слог.
        • 0
          Такие, наверное, да. Но для определенного кода нужен определенный уровень опыта и владения.
          К примеру, следующий код особенно нет смысла комментировать, он от этого не станет понятнее, тем не менее такой код можно часто встретить в библиотеках типа libstdc++/libc++/boost.
          template <typename It, typename Mapper>
          struct map_iterator : std::iterator<
          	typename It::iterator_category,
          	std::remove_reference_t<apply_t<It, Mapper>>,
          	std::ptrdiff_t,
          	std::add_pointer_t<std::remove_reference_t<apply_t<It, Mapper>>>,
          	apply_t<It, Mapper>>
          {
          	/// ...
          };
          
        • 0
          Код вполне очевиден, если прочитать названия метода и переменных. Если убрать лишние скобки и отформатировать нормально, то вполне ничего:

          bool ModelHandler::withinBoundaries(const ObjectPtr& obj) const {
              return -0.1 * _worldWidth  < obj->x() && obj->x() < _worldWidth  * 1.1 &&
                     -0.1 * _worldHeight < obj->y() && obj->y() < _worldHeight * 1.1;
          }


  • 0
    >например, про дерево отрезков, которое он же и независимо открыл одним из первых в мире и первый в России

    Ой-ой, что-то здесь сильно неправильно. По информации из Википедии, дерево отрезков было открыто в 1977 году — за 5 лет до рождения Михаила. Может быть, имело место переоткрытие? Все-таки не бог весть какая сложная структура данных. В любом случае, уверен, что и в мире, и в России, она была достаточно широко известна и до этого события.

    Думаю, кто-то что-то неправильно понял, и надо бы это предложение исправить.

    А Михаил крут и по большому количеству более достоверных причин)
    • +2
      Да, конечно, имеется ввиду независимое переоткрытие. Ответ Михаила:

      По моим сведениям в русскоязычной среде олимпиад по программированию эта структура данных не была известна примерно до 2000-го года. Я переоткрыл ее, применив впервые в 2000-м году, примерно тогда же сообразив про применения для групповых обновлений. Рассказав об этом Максиму Бабенко, получил отзыв, что ему такой подход раньше не встречался. Позже, на школьных сборах в Малоярославце обсудил первое применение дерева отрезков с Андреем Лопатиным, он тогда указал, что они начали его применять чуть позже (и по-моему тоже самостоятельно открыли).

      Вообще, тогда было замечательное время, когда известных идей и наработок было значительно меньше, и прям во время контестов появлялись свежие подходы. Как еще один пример, я слышал историю, что Николай Дуров самостоятельно переоткрыл алгоритм Эдмондса-Карпа нахождение потока.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка