Tag: algorithms

HOW DOOM FIRE WAS DONE

~ irrlab

The Game Engine Black Book: DOOM features a whole chapter about DOOM console ports and the challenges they encountered. The utter failure of the 3DO, the difficulties of the Saturn due to its affine texture mapping, and the amazing “reverse-engineering-from- scratch” by Randy Linden on Super Nintendo all have rich stories to tell.

Once heading towards disaster[1], the Playstation 1 (PSX) devteam managed to rectify course to produce a critically and commercially acclaimed conversion. Final DOOM was the most faithful port when compared to the PC version. The alpha blended colored sectors not only improved visual quality, they also made gameplay better by indicating the required key color. Sound was also improved via reverberation effects taking advantage of the PSX’s Audio Processing Unit.

The devteam did such a good job that they found themselves with a few extra CPU cycles they decided to use to generate animated fire both during both the intro and the gameplay. Mesmerized, I tried to find out how it was done. After an initial calling found no answer, I was about to dust off my MIPS book to rip open the PSX executable when Samuel Villarreal replied on Twitter to tell me he had already reverse-engineered the Nintendo 64 version[2]. I only had to clean, simplify, and optimize it a little bit.

It was interesting to re-discover this classic demoscene effect; the underlying idea is similar to the first water ripple many developers implemented as a programming kata in the 90’s. The fire effect is a vibrant testimony to a time when judiciously picked palette colors combined with a simple trick were the only way to get things done.

http://fabiensanglard.net/doom_fire_psx/

Advertisements

Problem Solving with Algorithms and Data Structures using Python

~ irrlab
  • To review the ideas of computer science, programming, and problem-solving.
  • To understand abstraction and the role it plays in the problem-solving process.
  • To understand and implement the notion of an abstract data type.
  • To review the Python programming language.

http://interactivepython.org/runestone/static/pythonds/index.html

190 universities just launched 600 free online courses. Here’s the full list

~ irrlab

If you haven’t heard, universities around the world are offering their courses online for free (or at least partially free). These courses are collectively called MOOCs or Massive Open Online Courses.

In the past six years or so, over 800 universities have created more than 10,000 of these MOOCs. And I’ve been keeping track of these MOOCs the entire time over at Class Central, ever since they rose to prominence.

In the past four months alone, 190 universities have announced 600 such free online courses. I’ve compiled a list of them and categorized them according to the following subjects: Computer Science, Mathematics, Programming, Data Science, Humanities, Social Sciences, Education & Teaching, Health & Medicine, Business, Personal Development, Engineering, Art & Design, and finally Science.

If you have trouble figuring out how to signup for Coursera courses for free, don’t worry — here’s an article on how to do that, too.

Many of these are completely self-paced, so you can start taking them at your convenience.

https://qz.com/1437623/600-free-online-courses-you-can-take-from-universities-worldwide/

Practical Text Classification With Python and Keras

~ irrlab

Imagine you could know the mood of the people on the Internet. Maybe you are not interested in its entirety, but only if people are today happy on your favorite social media platform. After this tutorial, you’ll be equipped to do this. While doing this, you will get a grasp of current advancements of (deep) neural networks and how they can be applied to text.

Reading the mood from text with machine learning is called sentiment analysis, and it is one of the prominent use cases in text classification. This falls into the very active research field of natural language processing (NLP). Other common use cases of text classification include detection of spam, auto tagging of customer queries, and categorization of text into defined topics. So how can you do this?

https://realpython.com/python-keras-text-classification/

Replacing the cache replacement algorithm in memcached

~ irrlab

In this post we delve into a reworking of memcached’s Least Recently Used (LRU) algorithm which was made default when 1.5.0 was released. Most of these features have been available via the “-o modern” switch for years. The 1.5.x series has enabled them all to work in concert to reduce RAM requirements.

When memcached was first deployed, it was typically co-located on backend web servers, using spare RAM and CPU cycles. It was important that it stay light on CPU usage while being fast; otherwise it would affect the performance of the application it was attempting to improve.

Over time, the deployment style has changed. There are frequently fewer dedicated nodes with more RAM, but spare CPU. On top of this web requests can fetch dozens to hundreds of objects at once, with the request latency having a greater overall impact.

This post is focused on the efforts to reduce the number of expired items wasting cache space, general LRU improvements, as well as latency consistency.

https://memcached.org/blog/modern-lru/