101 Basic Computer Games

@qbfan · Регистрация: 10.11.2019

Студворк — интернет-сервис помощи студентам

Недавно я натолкнулся в сети на книгу, о которой никогда не слышал.
Книга называется "101 Basic Computer Games". Она была выпущена DEC в 1975 году
и содержит тексты игр с аннотациями. Игры написаны на BASIC, на компьютере PDP-11.

Очень интересная коллекция для начинающих программистов, и не только.

Коллекция игр с описаниями и переводом на другие языки программирования находится по адресу:

https://github.com/coding-horr... uter-games

@Замабувараев · 29.06.2024, 07:18

Сообщение от Quiet Snow

А если надо портировать прогу в ограниченные условия, под микроконтроллер или под тот же DOS?

Я чёт сомневаюсь что GUI можно портировать под микроконтроллёры. Или какой‐нибудь сервер под DOS.

Сообщение от Quiet Snow

Ну да, если оптимизирующий, а если нет?

А зачем нужны неоптимизированные программы, которые медленно работают? Такты вхолостую гонять? Или чтобы говорили «хотите быструю программу — пишите на си»?
Ну разве что отладочная версия, где оптимизация только запутывает отладчик. А релизные версии они все должны быть компилированы с включённой оптимизацией.

Сообщение от Quiet Snow

Т.е. это не будешь считать bloatware?

Зависит от задачи. Для игр, видеомонтажа, аудиостудии, 3D моделирования, фотошопа, нейронных сетей такие цифры оправданы.

Сообщение от Quiet Snow

Кстати ты пробовал заводить 2 гигабайта?

Можно и 4 гигабайта. В любом случае максимум — это максимальное значение типа DWORD, которое указано в формате файла PE. 4 гигабайта.

@testuser2 · 29.06.2024, 09:48

Квиксорт линейный надо кому? Для реализации рекурсии вместо стека используется массив структур. Скорость у меня на vba получилась примерно эквивалентная рекурсивному варианту, но есть защита от "переполнения стека". Для типизации достаточно задать тип для переменной Field (массив), Ref и Temp

Кликните здесь для просмотра всего текста

Visual Basic
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
Private Type QSortData
    P1 As Long
    P2 As Long
    Lb As Long
    Ub As Long
    Mrk As Byte
End Type
 
Sub testQuickSort2()
    Dim i&, Arr1&(), Arr2&(), t0!, t1!, t2!
    ReDim Arr1(500000)
    Randomize
    For i = 0 To UBound(Arr1)
        Arr1(i) = Rnd * 10000
    Next
    
    Arr2 = Arr1
    t0 = Timer
    QuickSort2 Arr2
    t1 = Timer - t0
    
    Arr2 = Arr1
    t0 = Timer
    QuickSort Arr2, LBound(Arr2), UBound(Arr2)
    t2 = Timer - t0
    
    Debug.Print t1, t2
End Sub
 
Private Sub QuickSort2(Field)
    Const qBgn& = 255       'начальный размер стека
    Const qStp& = 256       'шаг увеличения стека
    Dim Ref, Tmp
    Dim lv&, lv2&, qUb&
    Dim QDt() As QSortData  'стек псевдо-рекурсии
    ReDim QDt(qBgn): qUb = qBgn
    
    QDt(lv).Lb = LBound(Field): QDt(lv).Ub = UBound(Field)
 
1   With QDt(lv)
      .P1 = .Lb: .P2 = .Ub
      Ref = Field((.P1 + .P2) / 2)
      
      Do
          Do While Field(.P1) < Ref
              .P1 = .P1 + 1
          Loop
          Do While Field(.P2) > Ref
              .P2 = .P2 - 1
          Loop
          If .P1 <= .P2 Then
              Tmp = Field(.P1)
              Field(.P1) = Field(.P2)
              Field(.P2) = Tmp
              .P1 = .P1 + 1
              .P2 = .P2 - 1
          End If
      Loop Until .P1 > .P2
    End With
    
    If QDt(lv).Lb < QDt(lv).P2 Then
        GoSub NxtLvl
'        lv2 = lv + 1
        QDt(lv2).Lb = QDt(lv).Lb: QDt(lv2).Ub = QDt(lv).P2
        QDt(lv).Mrk = 2
        lv = lv2
        GoTo 1
    End If
 
2   If QDt(lv).P1 < QDt(lv).Ub Then
        GoSub NxtLvl
'        lv2 = lv + 1
        QDt(lv2).Lb = QDt(lv).P1: QDt(lv2).Ub = QDt(lv).Ub
        QDt(lv).Mrk = 3
        lv = lv2
        GoTo 1
    End If
    
3   If lv Then
        lv = lv - 1
        On QDt(lv).Mrk GoTo 1, 2, 3
    End If
Exit Sub
NxtLvl: 'увеличиваем размер "стека" если его не хватает для создания следуюющего уровня рекурсии
    lv2 = lv + 1
    If qUb < lv2 Then
        qUb = qUb + qStp
        ReDim Preserve QDt(qUb)
    End If
Return
End Sub
'https://stackoverflow.com/questions/152319/vba-array-sort-function
Private Sub QuickSort(Field, ByVal Lb As Long, ByVal Ub As Long)
    Dim P1 As Long, P2 As Long
    Dim Ref, Tmp
    
    P1 = Lb: P2 = Ub
    Ref = Field((P1 + P2) / 2)
    Do
        Do While Field(P1) < Ref
            P1 = P1 + 1
        Loop
        Do While Field(P2) > Ref
            P2 = P2 - 1
        Loop
        If P1 <= P2 Then
            Tmp = Field(P1)
            Field(P1) = Field(P2)
            Field(P2) = Tmp
            P1 = P1 + 1
            P2 = P2 - 1
        End If
    Loop Until P1 > P2
    If Lb < P2 Then QuickSort Field, Lb, P2
    If P1 < Ub Then QuickSort Field, P1, Ub
End Sub

Результат теста

Code
1
 1,484375      1,46875

@Quiet Snow · 29.06.2024, 10:41

Сообщение от Замабувараев

А зачем нужны неоптимизированные программы, которые медленно работают? Такты вхолостую гонять?

А почему не учитывается то, что человек может уметь писать быстрые программы без оптимизирующих компиляторов?

Сообщение от Замабувараев

Или чтобы говорили «хотите быструю программу — пишите на си»?

Си это была тупо мода и понты и ты это знаешь, что всё зависит от программиста, а не от си.
Сейчас новая мода - пайтон, но си никуда не делся и по части оптимизации ему отдают предпочтение,
как и асму, на котором пишут вставки дельфисты, сишники и в общем то мы на бейсиках.
Через 10 лет будет ещё какое-нибудь новое говно. Это т.н. "мейнстрим" не более.
Чтобы привлечь аудиторию, т.к. чем больше комьюнити, тем больше разработок и плохих и хороших.

Сообщение от Замабувараев

Я чёт сомневаюсь что GUI можно портировать под микроконтроллёры. Или какой‐нибудь сервер под DOS.

GUI под DOS можно сделать, был даже сайт где разные извращенцы написали на Q\QuickBasic под сотню GUёв.
Там конечно почти всё - дрисня, но были интересные штуки. Вроде ссылку уже приводил.

Сообщение от Замабувараев

Для игр, видеомонтажа, аудиостудии, 3D моделирования, фотошопа, нейронных сетей такие цифры оправданы.

Это разные классы софта с разными сценариями.
Ну игра может сожрать 8-16 гигов, но нафига ей столько стека? В крайнем случае завести мегабайт 50.
DAW-у стек не нужен, насчёт монтажки не знаю, фотошопу в его базисе - точно стек не нужен в таких объёмах,
нейронки - не знаю, не писал и не обдумывал.
Монтажка это больше не совсем RT(там используется уменьшенный кадр предпросмотра), а вот игры и DAW -это RT
и там как минимум не подойдёт подход, про который ты часто говоришь т.е. заводить и уничтожать постоянно
память т.к. это будет давать фризы и микрофризы от которых наоборот стараются избавиться и закешировать
в память всё что только можно, лишь бы разгрузить проц и фреймтайм сделать меньше.

Сообщение от testuser2

Квиксорт линейный надо кому?

Это твой код? Первый результат - нерекурсивный?

@Замабувараев · 29.06.2024, 10:56

Сообщение от Quiet Snow

А почему не учитывается то, что человек может уметь писать быстрые программы без оптимизирующих компиляторов?

Потому что только оптимизирующий компилятор умеет выбрасывать прологи и эпилоги функций, встраивать функции, раскидывать переменные по регистрам, знает особенности архитектуры процессора. Очень много опций оптимизации.

@testuser2 · 29.06.2024, 11:23

Сообщение от Quiet Snow

Это твой код? Первый результат - нерекурсивный?

1)Да мой, это просто переделка рекурсивного варианта, как бы с имитацией повторных вызовов и заполнением стека аргументов.
2)Да, без использования повторных вызовов процедуры.

@CoderHuligan · 29.06.2024, 11:23

Сообщение от Замабувараев

Ну во‐первых, память под стэк только резервируется, а выделяется по требованию.

И в каком это языке так?

Сообщение от Замабувараев

ОС не имеет права портить данные.

А речь не об ОС и аппаратном стеке адресуемом esp. Опять речь идет об ЯП, который по идее должен освобождать нас от особенностей машины.

Сообщение от Замабувараев

Так это уже придумано: и называется Sub

То что вы привели это процедура. Это не тоже самое что просто блок кода в виде состояния (шаг алгоритма). Не путать с шагами инструкций языка.

Сообщение от locm

При вашем методе они тоже будут.

Они везде будут. Метод позволяет доказывать правильность алгоритмов. Это резко снизит количество ошибок.

Сообщение от locm

Почему присваивание должно приводить к переходу?

Потому что должна существовать переменная, которая отслеживает (запоминает) текущее состояние. Дейкстра кстати к этому пришел в конце концов, но было уже поздно. Он писал о необходимости иметь отдельную переменную, которая отслеживала бы отдельные шаги алгоритма. Не я это придумал. Что это дает? Много чего.
1. Попадая в новое состояние (блок кода логически являющийся шагом алгоритма), текущий блок может "вспомнить" предыдущее состояние, если завести еще одну переменную. Отпадает нужда во флагах.
2. процедура реализующая алгоритм может принимать состояние как аргумент и переходить сразу в конкретное состояние без необходимости в переключателях. Код становится более лаконичным и быстрым.
3. возможно протоколирование работы алгоритма в целях отладки и верификации правильности его работы, даже в ран-тайм.
4. благодаря переменной возможно осуществлять неявный переход, что я и показал на примере. То есть, полностью отпадает нужда в безусловных переходах. А в конце блока-состояния по умолчанию переход в то состояние, в котором находиться переменная.
5. изолирует программиста от особенностей архитектуры, так как он оперирует понятием переменной, а не переходом. при этом всегда может "потрогать" состояние ведь оно всегда зашито в переменной.

Сообщение от locm

Это точно не бейсик!

Это прямое развитие бейсика.

@locm · 29.06.2024, 11:23

Сообщение от Замабувараев

Я чёт сомневаюсь что GUI можно портировать под микроконтроллёры.

Можно https://www.youtube.com/watch?v=c6Muj213PNs
Но это сложнее чем для компов из-за ограниченности ресурсов и отсутствия ОС.

@Quiet Snow · 29.06.2024, 11:30

Сообщение от Замабувараев

Потому что только оптимизирующий компилятор умеет выбрасывать прологи и эпилоги функций

Почему? Есть же опции Naked для FB.
https://documentation.help/Fre... Naked.html

Naked allows the programmer to write procedures without the compiler generating any prolog/epilog code.

Сообщение от Замабувараев

раскидывать переменные по регистрам

Это и человек прекрасно делает.

По особенностям архитектуры - соглашусь, не каждый имеет богатый опыт оптимизации для разных кешей
и пайплайнов.
В принципе из всего озвученного только особенности архитектуры, разворот циклов и не упомянутое
выравнивание даёт самый очевидный видимый эффект, а дальше влияет уже работа человека с алгоритмом.
Ну ещё всякие математические оптимизации, хотя это уже очень спорная вещь и на это я бы точно не стал
полагаться.

@The trick · 29.06.2024, 11:32

Есть ещё LVGL графическая либа с виджетами для мк.

@Quiet Snow · 29.06.2024, 11:57

Сообщение от CoderHuligan

Дейкстра кстати к этому пришел в конце концов, но было уже поздно. Он писал о необходимости иметь отдельную переменную, которая отслеживала бы отдельные шаги алгоритма. Не я это придумал. Что это дает? Много чего.

Этот упырь много чего писал и "пистел"... Поздно было когда товарищ "профессор" не осилил
авто реструктуризацию, потому оставалось только подставить бедолагу Вирта и "трепаться" дальше
на особо доверчивые ухи...

Сообщение от testuser2

1)Да мой, это просто переделка рекурсивного варианта, как бы с имитацией повторных вызовов и заполнением стека аргументов.

За 1 сутки сваял?

Сообщение от CoderHuligan

И в каком это языке так?

Замабувараев про виртуальную память винды и других ОС где этот механизм используется.

Сообщение от CoderHuligan

процедура реализующая алгоритм может принимать состояние как аргумент и переходить сразу в конкретное состояние без необходимости в переключателях.

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

@testuser2 · 29.06.2024, 12:04

Сообщение от Quiet Snow

За 1 сутки сваял?

да млн за секунду! ))

@locm · 29.06.2024, 12:26

Сообщение от CoderHuligan

Метод позволяет доказывать правильность алгоритмов. Это резко снизит количество ошибок.

Вы сами поняли что написали?

Сообщение от Quiet Snow

Это и человек прекрасно делает.

На асме?
Его проблема в том что он сильно платформозависимый. Даже порт с x86 на x64 требует немалой корректировки кода, не говоря про порт на ARM где переписать нужно все!
ARM сейчас много где используется в том числе в ноутбуках. https://lifehacker.ru/arm-noutbuki/
https://www.ixbt.com/news/2024... gon-x.html

@CoderHuligan · 29.06.2024, 12:27

Сообщение от Quiet Snow

Замабувараев про виртуальную память винды и других ОС где этот механизм используется.

Про файл подкачки, что ли? А какое это отношение имеет к языкам программирования? только сильно опосредованое.

Сообщение от Quiet Snow

Если это как-то вообще можно понять без примеров и подробностей - то это очень трудно понять,

Я понимаю, что трудно. Мозг привык мыслить другими категориями. Вернее так нас приучили. Хотя концепция проста как паренная репа. Примеры нужны. Но не для данной темы. В блоге у себя я все это опишу, как смогу.

@testuser2 · 29.06.2024, 12:45

Сообщение от CoderHuligan

2. процедура реализующая алгоритм может принимать состояние как аргумент и переходить сразу в конкретное состояние без необходимости в переключателях. Код становится более лаконичным и быстрым.

Вот да, это была бы классная вещь, как бы переход на метку, но если бы метку можно было задавать значением переменной. Goto var. В VB есть такая конструкция (может быть в QB тоже есть х.з.) On var Goto метка1, метка2, метка3. Это конечно не то, но работает по быстрее чем Select и If

@CoderHuligan · 29.06.2024, 13:22

Сообщение от locm

Вы сами поняли что написали?

Абсолютно. Вот как вы это доказываете я просто не представляю. Хотя кто сейчас этим заморачивается..

Сообщение от testuser2

On var Goto метка1, метка2, метка3. Это конечно не то, но работает по быстрее чем Select и If

Совершенно верно. Это переход по адресам меток. В фортране был вычисляемый goto и арифметический if - классные штуки. А GCC позволяет брать адреса на метки. Но это всё довольно низкоуровневые фичи.

@locm · 29.06.2024, 13:36

Сообщение от CoderHuligan

Абсолютно.

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

@testuser2 · 29.06.2024, 14:03

Чуть оптимизировал

Кликните здесь для просмотра всего текста

Visual Basic
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
62
63
Private Sub QuickSort2(Field&())
    Const qBgn& = 255       'начальный размер стека
    Const qStp& = 256       'шаг увеличения стека
    Dim Ref&, Tmp&
    Dim lv&, lv2&, qUb&
    Dim QDt() As QSortData  'стек псевдо-рекурсии
    ReDim QDt(qBgn): qUb = qBgn
    
    QDt(lv).Lb = LBound(Field): QDt(lv).Ub = UBound(Field)
 
1   With QDt(lv)
      .P1 = .Lb: .P2 = .Ub
      Ref = Field((.P1 + .P2) / 2)
      
      Do
          Do While Field(.P1) < Ref
              .P1 = .P1 + 1
          Loop
          Do While Field(.P2) > Ref
              .P2 = .P2 - 1
          Loop
          If .P1 <= .P2 Then
              Tmp = Field(.P1)
              Field(.P1) = Field(.P2)
              Field(.P2) = Tmp
              .P1 = .P1 + 1
              .P2 = .P2 - 1
          End If
      Loop Until .P1 > .P2
    
      If .Lb < .P2 Then
          GoSub NxtLvl ' lv2 = lv + 1
          QDt(lv2).Lb = .Lb: QDt(lv2).Ub = .P2
          .Mrk = 2
          lv = lv2
          GoTo 1
      End If
    End With
    
2   With QDt(lv)
      If .P1 < .Ub Then
          GoSub NxtLvl ' lv2 = lv + 1
          QDt(lv2).Lb = .P1: QDt(lv2).Ub = .Ub
          .Mrk = 3
          lv = lv2
          GoTo 1
      End If
    End With
    
3   If lv Then
        lv = lv - 1
        On QDt(lv).Mrk GoTo 1, 2, 3
    End If
    
Exit Sub
NxtLvl: 'увеличиваем размер стека если его не хватает для создания следуюющего уровня рекурсии
    lv2 = lv + 1
    If qUb < lv2 Then
        qUb = qUb + qStp
        ReDim Preserve QDt(qUb)
    End If
Return
End Sub

Code
1
 0,578125      1,492188

@Quiet Snow · 29.06.2024, 14:07

Сообщение от CoderHuligan

Мозг привык мыслить другими категориями.

Это не означает, что что-то новое лучше и никогда не означало.

Сообщение от CoderHuligan

Примеры нужны. Но не для данной темы. В блоге у себя я все это опишу, как смогу.

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

Сообщение от locm

Даже порт с x86 на x64 требует немалой корректировки кода

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

Сообщение от testuser2

да млн за секунду! ))

Ну так написал же:

Сообщение от testuser2

Я квик-сорт пробовал переделать в линейку когда-то, не получилось

"Когда-то" это значит не сейчас, а это значит что переделывал после этого поста. Или не?

@testuser2 · 29.06.2024, 14:32

Сообщение от Quiet Snow

"Когда-то" это значит не сейчас, а это значит что переделывал после этого поста. Или не?

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

Добавлено через 9 минут

Сообщение от testuser2

проще именно имитировать работу стека.

Притом не только стека аргументов функции, но и ее внутренних переменных.

@The trick · 29.06.2024, 14:59

Сообщение от CoderHuligan

Совершенно верно. Это переход по адресам меток. В фортране был вычисляемый goto и арифметический if - классные штуки. А GCC позволяет брать адреса на метки. Но это всё довольно низкоуровневые фичи.

Так и работает Select Case (switch в C).

Новые блоги и статьи Все статьи Все блоги /
Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .	Как надо было делать правильно - вообще не слушать ИИ, его дело - текст. Hrethgir 15.07.2026 А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её. Всё это стресс конечно. Почему?. . .	Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет	Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .

@qbfan Модератор 1245 / 676 / 292 Регистрация: 10.11.2019 Сообщений: 1,406

	101 Basic Computer Games 25.05.2024, 16:17. Показов 18770. Ответов 273 Метки нет (Все метки) Недавно я натолкнулся в сети на книгу, о которой никогда не слышал. Книга называется "101 Basic Computer Games". Она была выпущена DEC в 1975 году и содержит тексты игр с аннотациями. Игры написаны на BASIC, на компьютере PDP-11. Очень интересная коллекция для начинающих программистов, и не только. Коллекция игр с описаниями и переводом на другие языки программирования находится по адресу: https://github.com/coding-horr... uter-games 4

@The trick Модератор 10061 / 3906 / 885 Регистрация: 22.02.2013 Сообщений: 5,856 Записей в блоге: 79
	29.06.2024, 11:32
	Есть ещё LVGL графическая либа с виджетами для мк. 0